Paper Info
Title
Approximability and hardness in multi-objective optimization
Abstract
We study the approximability and the hardness of combinatorial multi-objective NP optimization problems (multi-objective problems, for short). Our contributions are: - We define and compare several solution notions that capture reasonable algorithmic tasks for computing optimal solutions. - These solution notions induce corresponding NP-hardness notions for which we prove implication and separation results. - We define approximative solution notions and investigate in which cases polynomial-time solvability translates from one to another notion. Moreover, for problems where all objectives have to be minimized, approximability results translate from single-objective to multi-objective optimization such that the relative error degrades only by a constant factor. Such translations are not possible for problems where all objectives have to be maximized (unless P = NP). As a consequence we see that in contrast to single-objective problems (where the solution notions coincide), the situation is more subtle for multiple objectives. So it is important to exactly specify the NP-hardness notion when discussing the complexity of multi-objective problems.
Year
DOI
Venue
2010
10.1007/978-3-642-13962-8_20
CiE
Keywords
Field
DocType
constant factor,approximability result,multi-objective optimization,np-hardness notion,optimal solution,corresponding np-hardness notion,multiple objective,solution notion,reasonable algorithmic task,multi-objective problem,approximative solution notion,multi objective optimization,relative error,optimization problem,polynomial time
Discrete mathematics,Combinatorics,Mathematical optimization,Np optimization problems,Computer science,L-reduction,Multi-objective optimization,Vertex cover,Approximation error,Multivalued function
Conference
Volume
ISSN
ISBN
6158
0302-9743
3-642-13961-2
Citations 
PageRank 
References 
8
0.55
8
Authors
4
Name
Order
Citations
PageRank
Christian Glaßer117524.52
Christian Reitwießner2394.81
Heinz Schmitz3172.46
Maximilian Witek4253.71