Algorithms to Approximate Column-sparse Packing Problems
Algorithms to Approximate Column-sparse Packing Problems
复制标题
DOI：
10.1145/3355400
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Brian Brubach;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
中科院分区：
文献类型：
--
作者：
Brian Brubach;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
在确定性和随机离散优化的几种情况下，列型填料问题都会出现。作为三个主要示例，我们获得了k-Column-Sparme-Sparse包装整数程序的已知LP松弛度（Bansal等人，计算理论，2012年）和随机K-set填料（ Bansal等人，Algorithmica，2012年），并将“剩余距离一半”达到最佳状态，以实现HyperGraph匹配的Füredi，Kahn和Seymour的主要完整性跨度猜想（Combinatorica，1993）。
Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column-sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go “half the remaining distance” to optimal for a major integrality-gap conjecture of Füredi, Kahn, and Seymour on hypergraph matching (Combinatorica, 1993).