The LP-rounding plus greed approach for partial optimization revisited
The LP-rounding plus greed approach for partial optimization revisited
复制标题
重新审视用于部分优化的 LP 舍入加贪婪方法
DOI：
10.1007/s11704-020-0368-3
复制
发表时间：
2021-09
影响因子：
4.2
通讯作者：
Peng Zhang
中科院分区：
文献类型：
--
作者：
Peng Zhang
有许多优化问题具有以下共同性质：给定一个由许多子任务组成的总任务，问题要求找到一个解决方案来完成这些子任务的一部分。例如k-森林问题和k-多割问题等，这些问题被称为部分优化问题，通常是NP-困难的。本文系统地研究了部分优化问题的近似算法设计方法--LP-舍入加贪婪法。该方法简单、强大且通用。我们展示了如何使用这种方法来设计近似算法的k-森林问题，k-多割问题，k-广义连通性问题，等等。
There are many optimization problems having the following common property: Given a total task consisting of many subtasks, the problem asks to find a solution to complete only part of these subtasks. Examples include thek-Forest problem and thek-Multicut problem, etc. These problems are called partial optimization problems, which are often NP-hard. In this paper, we systematically study the LP-rounding plus greed approach, a method to design approximation algorithms for partial optimization problems. The approach is simple, powerful and versatile. We show how to use this approach to design approximation algorithms for thek-Forest problem, thek-Multicut problem, thek-Generalized connectivity problem, etc.
登录
查看更多内容
DOI：
10.1145/167088.167266
发表时间：
1993-06
期刊：
Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Naveen Garg;V. Vazirani;M. Yannakakis
通讯作者：
Naveen Garg;V. Vazirani;M. Yannakakis
DOI：
10.1007/978-3-642-14165-2_42
发表时间：
2010-07
期刊：
--
影响因子：
--
作者：
F. Grandoni;T. Rothvoss
通讯作者：
F. Grandoni;T. Rothvoss
DOI：
--
发表时间：
2003-01
期刊：
--
影响因子：
--
作者：
Anupam Gupta
通讯作者：
Anupam Gupta
影响因子：
1.1
作者：
JOHNSON, DS
通讯作者：
JOHNSON, DS
影响因子：
3.7
作者：
Aditya Bhaskara;M. Charikar;E. Chlamtác;U. Feige;Aravindan Vijayaraghavan
通讯作者：
Aditya Bhaskara;M. Charikar;E. Chlamtác;U. Feige;Aravindan Vijayaraghavan