Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959667 | European Journal of Operational Research | 2017 | 38 Pages |
Abstract
We study the connection between reference point methods and approximation algorithms for multicriteria optimization problems over discrete sets. In particular, we establish that, in terms of computational complexity, computing approximate reference point solutions is polynomially equivalent to approximating the Pareto set. Complementing these results, we show for a number of general algorithmic techniques in single criteria optimization how they can be lifted to reference point optimization. In particular, we lift the link between dynamic programming and FPTAS, as well as certain LP-rounding techniques. The latter applies, e.g., to Set Cover and several machine scheduling problems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Christina Büsing, Kai-Simon Goetzmann, Jannik Matuschke, Sebastian Stiller,