Dynamic programming multi-objective combinatorial optimization
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.
- Dynamic programming bi-criteria combinatorial optimization
- On a biobjective search problem in a line: formulations and algorithms
- Extensions of dynamic programming for multi-stage combinatorial optimization
- Dynamic programming for a biobjective search problem in a line
- scientific article; zbMATH DE number 43711
- Bucket elimination for multiobjective optimization problems
- Polyhedral Characterization of Discrete Dynamic Programming
- The principle of optimality in the design of efficient algorithms
- scientific article; zbMATH DE number 863497
- Optimization of dynamic programming methods when solving extremal combinatorial problems
- Integrating Pareto optimization into dynamic programming
- Extensions of dynamic programming for multi-stage combinatorial optimization
- Time dependency in multiple objective dynamic programming
- Combinatorial data analysis. Optimization by dynamic programming
- scientific article; zbMATH DE number 6003201 (Why is no real title available?)
- Dynamic programming for a biobjective search problem in a line
- Global optimization for Heilbronn problem of convex polygons based on bilinear matrix inequalities solving
- Dynamic programming and the Lagrange multipliers
- Dynamic programming bi-criteria combinatorial optimization
- Generalized dynamic programming for multicriteria optimization
This page was built for publication: Dynamic programming multi-objective combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2218697)
