TY - JOUR

T1 - Dynamic programming bi-criteria combinatorial optimization

AU - Mankowski, Michal

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST), Kingdom of Saudi Arabia . We are greatly indebted to the anonymous reviewers for useful comments and suggestions.

PY - 2020/4/29

Y1 - 2020/4/29

N2 - We introduce a model for combinatorial optimization problems based on the notion of a circuit. This circuit builds a set of elements for optimization from one-element sets attached to input nodes. It uses the operation of union of sets and functional operations on elements extended to sets of elements. We design a dynamic programming algorithm based on this circuit which constructs the set of Pareto optimal points for the problem of bi-criteria optimization of elements described by the circuit relative to two cost functions. We tested this approach on nine known combinatorial optimization problems. The problems related to the matrix chain multiplication, optimal paths in directed graphs, and binary search trees are considered in detail.

AB - We introduce a model for combinatorial optimization problems based on the notion of a circuit. This circuit builds a set of elements for optimization from one-element sets attached to input nodes. It uses the operation of union of sets and functional operations on elements extended to sets of elements. We design a dynamic programming algorithm based on this circuit which constructs the set of Pareto optimal points for the problem of bi-criteria optimization of elements described by the circuit relative to two cost functions. We tested this approach on nine known combinatorial optimization problems. The problems related to the matrix chain multiplication, optimal paths in directed graphs, and binary search trees are considered in detail.

UR - http://hdl.handle.net/10754/662698

UR - https://linkinghub.elsevier.com/retrieve/pii/S0166218X20301864

UR - http://www.scopus.com/inward/record.url?scp=85083894361&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.04.016

DO - 10.1016/j.dam.2020.04.016

M3 - Article

SN - 0166-218X

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -