Dynamic programming bi-criteria combinatorial optimization

Michal Mankowski*, Mikhail Moshkov

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)513-533
Number of pages21
JournalDiscrete Applied Mathematics
Volume284
DOIs
Publication statusPublished - 30 Sep 2020
Externally publishedYes

Fingerprint

Dive into the research topics of 'Dynamic programming bi-criteria combinatorial optimization'. Together they form a unique fingerprint.

Cite this