Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951933 | Theoretical Computer Science | 2017 | 34 Pages |
Abstract
Moreover, we show that our method can be extended to compute an (뱉
(1+2ϵ),αâ
(1+2ϵ))-approximate Pareto curve under the same assumptions. Our technique applies to many minimization problems to which most previous algorithms for computing approximate Pareto curves cannot be applied because the corresponding gap problem is NP-hard to solve. For maximization problems, however, we show that approximation results similar to the ones presented here for minimization problems are impossible to obtain in polynomial time unless P=NP.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Pascal Halffmann, Stefan Ruzika, Clemens Thielen, David Willems,