论文标题
基于本地搜索的设置覆盖方法
A Local Search-Based Approach for Set Covering
论文作者
论文摘要
在设定盖问题中，我们给了一个设置系统，每组都有一个重量，我们希望找到覆盖宇宙的集合，同时总重量较低。有几种已知的方法（基于贪婪的方法，放松和双拟合），可以实现此问题的$ H_K \ ln K + O（1）$（1）$（1）$（1）$（1）$近似值，其中每组的大小由$ K $界定。此外，获得$ \ ln k -o（\ ln \ ln k）$近似很难。 真相在哪里？我们可以缩小上限和下限之间的差距吗？对于$ k $的少量值，通常将改进尤其有趣，这通常用于套装和其他组合优化问题之间的减少。 我们考虑了一种非整体的本地搜索方法：据我们所知，这为设置封面提供了第一个$ H_K $ -Approximation，该方法使用基于本地搜索的方法提供了套装。我们的证明符合一页，并给出了完整的差距结果。通过考虑更大的动作和优化的潜在功能来完善我们的方法，从而给出了$（H_K -ω（\ log^2 K）/K）$ - 近似值，在$（H_K -ω（1/K^8））$（\ emph {R. \ \ \ \ \ \ \ hassin and A. \ hassin and A. \ levin，sicomp '05} Alg上的先前界面上有所改善。
In the Set Cover problem, we are given a set system with each set having a weight, and we want to find a collection of sets that cover the universe, whilst having low total weight. There are several approaches known (based on greedy approaches, relax-and-round, and dual-fitting) that achieve a $H_k \approx \ln k + O(1)$ approximation for this problem, where the size of each set is bounded by $k$. Moreover, getting a $\ln k - O(\ln \ln k)$ approximation is hard. Where does the truth lie? Can we close the gap between the upper and lower bounds? An improvement would be particularly interesting for small values of $k$, which are often used in reductions between Set Cover and other combinatorial optimization problems. We consider a non-oblivious local-search approach: to the best of our knowledge this gives the first $H_k$-approximation for Set Cover using an approach based on local-search. Our proof fits in one page, and gives a integrality gap result as well. Refining our approach by considering larger moves and an optimized potential function gives an $(H_k - Ω(\log^2 k)/k)$-approximation, improving on the previous bound of $(H_k - Ω(1/k^8))$ (\emph{R.\ Hassin and A.\ Levin, SICOMP '05}) based on a modified greedy algorithm.
