ISBN 9783843950060

978-3-8439-5006-0, Reihe Mathematik

Arne Herzel
Approximation Methods for Multiobjective and Parametric Optimization Problems

223 Seiten, Dissertation Technische Universität Kaiserslautern (2021), Hardcover, A5

Zusammenfassung / Abstract

In both multiobjective optimization problems and parametric optimization problems, it is impossible to provide a single solution in order to adequately solve the optimization problem. Instead, a set of solutions is sought that contains, for each possible compromise between the objective functions, or, for each possible value of the parameter vector, a corresponding optimal solution. Since such a set often requires an exponential or even infinite number of solutions, which rules out an efficient computation, it is reasonable to consider approximations for multiobjective and parametric optimization problems. An approximation is a set of solutions that contains, for each compromise between objectives, or, for each parameter vector, a solution that differs from a corresponding optimal solution by at most a given factor. As this is achievable with substantially fewer solutions, an efficient computation of approximations is often possible. For multiobjective optimization problems, the existence of polynomial-cardinality (1,1+eps,...,1+eps)-approximations is shown under very weak assumptions. The polynomial-time computability of such approximations is fully characterized – in general as well as with additional cardinality requirements – and corresponding approximation algorithms are presented. Moreover, the best-possible approximation guarantee with respect to an alternative, more precise measure of approximation is characterized. Further, for biobjective problems, a general theory is developed that describes how approximation properties with respect to general ordering cones can be transfered to the notion of approximation that is prevalent in the literature. For parametric optimization problems, similar questions regarding the efficient computability and cardinality of approximations are answered. For the first time, approximation algorithms are provided that are applicable to a general class of parametric optimization problems under weak assumptions.