Dynamic programming multi-objective combinatorial optimization (Q2218697)

This book presents a generalized dynamic programming approach for multi-objective combinatorial optimization problems. The approach is based on the notion of a circuit. In the first part of the book, the authors discuss the basic concepts which were first introduced in [the authors, Discrete Appl. Math. 284, 513--533 (2020; Zbl 1446.90139)]. In the second part, the proposed approach is demonstrated on nine problems such as matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, optimal bitonic tour, segmented least squares, convex polygon triangulation, one-dimensional clustering, and line breaking (text justification). The third part is devoted to matching optimization in trees. The authors propose and test algorithms for multi-stage and bi-criteria optimization of matching in trees. In the final forth part, the authors form syntactical circuits without repetitions for the problem of matching optimization in trees and for the 0/1 knapsack problem. They analyze the time complexity of the developed algorithms and provide experimental results.