A General Approximation Method for Bicriteria Minimization Problems
A General Approximation Method for Bicriteria Minimization Problems
复制标题
双准则最小化问题的通用逼近方法
DOI：
10.1016/j.tcs.2017.07.003
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
David Willems
中科院分区：
文献类型：
--
作者：
Pascal Halffmann;Stefan Ruzika;Clemens Thielen;David Willems
我们提出了一种用正值、多项式可计算目标函数来逼近双标准最小化问题的通用技术。给定 0< ϵ≤ 1 以及相应加权和问题的多项式时间 α 近似算法，我们展示了如何获得预算受限问题的双标准 (α⋅(1+ 2 ϵ), α⋅(1+ 2 ϵ)) 近似算法，其运行时间是输入编码长度的多项式且在 1 ϵ 中呈线性。此外，我们证明我们的方法可以扩展到在相同的假设下计算 (α⋅(1+ 2 ϵ), α⋅(1+ 2 ϵ)) 近似帕累托曲线。我们的技术适用于许多最小化问题，而大多数先前计算近似帕累托曲线的算法都无法应用到这些最小化问题，因为相应的间隙问题是 NP 难解的。然而，对于最大化问题，我们表明除非 P= NP，否则不可能在多项式时间内获得类似于此处针对最小化问题提出的近似结果。
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+ 2 ϵ))-approximation algorithm for the budget-constrained problem whose running time is polynomial in the encoding length of the input and linear in 1 ϵ. 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.
登录
查看更多内容
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Christian Glaer;Christian Reitwiener;M. Witek
通讯作者：
M. Witek
更快的确定性最大流量算法
DOI：
--
发表时间：
1992
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Valerie King;S. Rao;R. Tarjan
通讯作者：
R. Tarjan
二标准度量旅行商的改进和去随机近似
DOI：
--
发表时间：
2009
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Christian Glaßer;Christian Reitwießner;M. Witek
通讯作者：
M. Witek
DOI：
--
发表时间：
2010
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Christian Glaßer;Christian Reitwießner;Heinz Schmitz;M. Witek
通讯作者：
M. Witek
约束最短路径及相关问题
DOI：
--
发表时间：
2001
期刊：
影响因子：
--
作者：
M. Ziegelmann
通讯作者：
M. Ziegelmann