Reference points and approximation algorithms in multicriteria discrete optimization

doi:10.1016/j.ejor.2016.05.027

Reference points and approximation algorithms in multicriteria discrete optimization

2017-08-01

8

PRE

AI

C

Christina Büsing

K

Kai-Simon Goetzmann *

DOI：10.1016/j.ejor.2016.05.027

Original

Original request for help

Save

Abstract

En 中文

Mathematical research on multicriteria optimization problems predominantly revolves around the set of Pareto optimal solutions. In practice, on the other hand, methods that output a single solution are more widespread. Reference point methods are a successful example of this approach and are widely used in real-world multicriteria optimization. A reference point solution is the solution closest to a given reference point in the objective space. 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. (C) 2016 Elsevier B.V. All rights reserved.

Keywords:

Multicriteria optimization

Approximation algorithms

Reference point methods

Compromise programming

Combinatorial optimization

Reference points and approximation algorithms in multicriteria discrete optimization

Abstract

AI Summary

Journal

Organization