Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems
Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems
复制标题
NP-Hard 优化问题的一些密集实例的多项式时间逼近方案
DOI：
10.1007/s00453-001-0012-z
复制
发表时间：
2001
期刊：
影响因子：
1.1
通讯作者：
Marek Karpinski
中科院分区：
文献类型：
--
作者：
Marek Karpinski
抽象的。我们调查最近的结果存在的多项式时间近似计划的一些密集的NP-难组合优化问题的情况。我们指出了一些固有的限制存在这样的计划，为其他一些密集的优化问题的情况。我们还超越了稠密优化问题，并展示了如何使用稠密技术解决其他近似问题。
Abstract. We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard combinatorial optimization problems. We indicate some inherent limits for the existence of such schemes for some other dense instances of optimization problems. We also go beyond the dense optimization problems and show how other approximation problems can be solved by using dense techniques.