Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search
Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search
复制标题
DOI：
10.1109/focs.2013.61
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
Marek Cygan
中科院分区：
文献类型：
--
作者：
Marek Cygan
最自然的优化问题之一是 k-SET PACKING 问题，其中给定一组大小最多为 k 的集合，应该选择成对不相交集合的最大大小子族。 3-SET PACKING 的一个特例是众所周知的 3-DIMENSIONAL MATCHING 问题，它是 3-uniform tripartite hypergraphs 中的最大超匹配问题。这两个问题都属于卡普 21 个 NP 完全问题列表。 k-SET PACKING 最著名的多项式时间近似比是 (k + ε)/2，这可以追溯到 Hurkens 和 Schrijver [SIDMA'89] 的工作，它给出了 3 维匹配的 (1.5+ε) 近似值。这些结果是通过简单的本地搜索算法获得的，该算法使用恒定大小的交换。本文的主要结果是一种本地搜索 k-SET PACKING 的新方法，其中仅考虑一种特殊类型的交换，我们将其称为有界路径宽度的交换。我们证明，对于 k 的固定值，可以在 crpoly(|F|) 时间内搜索恒定路径宽度的 r 大小交换空间。此外，我们提出了一项分析，证明相对于恒定路径宽度的 O(log |F|) 大小交换的局部搜索最大值会产生多项式时间 (k+1+ε)/3 逼近算法，从而提高 k-SET PACKING 的最佳已知逼近率。特别是，我们将 3 维匹配的近似率从 3/2+ε 提高到 4/3+ε。
One of the most natural optimization problems is the k-SET PACKING problem, where given a family of sets of size at most k one should select a maximum size subfamily of pairwise disjoint sets. A special case of 3-SET PACKING is the well known 3-DIMENSIONAL MATCHING problem, which is a maximum hypermatching problem in 3-uniform tripartite hypergraphs. Both problems belong to the Karp's list of 21 NP-complete problems. The best known polynomial time approximation ratio for k-SET PACKING is (k + ε)/2 and goes back to the work of Hurkens and Schrijver [SIDMA'89], which gives (1.5+ε)-approximation for 3-DIMENSIONAL MATCHING. Those results are obtained by a simple local search algorithm, that uses constant size swaps. The main result of this paper is a new approach to local search for k-SET PACKING where only a special type of swaps is considered, which we call swaps of bounded pathwidth. We show that for a fixed value of k one can search the space of r-size swaps of constant pathwidth in crpoly(|F|) time. Moreover we present an analysis proving that a local search maximum with respect to O(log |F|)-size swaps of constant pathwidth yields a polynomial time (k+1+ε)/3-approximation algorithm, improving the best known approximation ratio for k-SET PACKING. In particular we improve the approximation ratio for 3-DIMENSIONAL MATCHING from 3/2+ε to 4/3+ε.