ECCC-Report TR10-031https://eccc.weizmann.ac.il/report/2010/031Comments and Revisions published for TR10-031en-usFri, 05 Mar 2010 09:25:56 +0200
Paper TR10-031
| Hardness and Approximability in Multi-Objective Optimization |
Christian Glaßer,
Christian Reitwießner,
Heinz Schmitz,
Maximilian Witek
https://eccc.weizmann.ac.il/report/2010/031We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short).
We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and to define corresponding NP-hardness notions. For both we prove reducibility and separation results.
Furthermore, we define approximative solution notions and investigate in which cases polynomial-time solvability translates from one to another notion. 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.
Fri, 05 Mar 2010 09:25:56 +0200https://eccc.weizmann.ac.il/report/2010/031