TY - JOUR

T1 - A general approximation method for bicriteria minimization problems

AU - Halffmann, Pascal

AU - Ruzika, Stefan

AU - Thielen, Clemens

AU - Willems, David

N1 - Publisher Copyright:
© 2017 Elsevier B.V.

PY - 2017/9/26

Y1 - 2017/9/26

N2 - We present a general technique for approximating bicriteria minimization problems with positive-valued, polynomially computable objective functions. Given 0<ϵ≤1 and a polynomial-time α-approximation algorithm for the corresponding weighted sum problem, we show how to obtain a bicriteria (α⋅(1+2ϵ),α⋅(1+[Formula presented]))-approximation algorithm for the budget-constrained problem whose running time is polynomial in the encoding length of the input and linear in [Formula presented]. Moreover, we show that our method can be extended to compute an (α⋅(1+2ϵ),α⋅(1+[Formula presented]))-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.

AB - We present a general technique for approximating bicriteria minimization problems with positive-valued, polynomially computable objective functions. Given 0<ϵ≤1 and a polynomial-time α-approximation algorithm for the corresponding weighted sum problem, we show how to obtain a bicriteria (α⋅(1+2ϵ),α⋅(1+[Formula presented]))-approximation algorithm for the budget-constrained problem whose running time is polynomial in the encoding length of the input and linear in [Formula presented]. Moreover, we show that our method can be extended to compute an (α⋅(1+2ϵ),α⋅(1+[Formula presented]))-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.

KW - Approximate Pareto curve

KW - Bicriteria approximation algorithm

KW - Multicriteria optimization

UR - http://www.scopus.com/inward/record.url?scp=85024497877&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2017.07.003

DO - 10.1016/j.tcs.2017.07.003

M3 - Article

AN - SCOPUS:85024497877

SN - 0304-3975

VL - 695

SP - 1

EP - 15

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -