Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
复制标题
2023 年年度 ACM-SIAM 离散算法研讨会 (SODA) 论文集
DOI：
10.1137/1.9781611977554.ch42
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Thiery T
中科院分区：
文献类型：
--
作者：
Thiery T
我们考虑加权k-集装箱问题，在这个问题中，我们给出一个加权集的集合，每个加权集最多有k个元素，并且必须返回一个具有最大总权重的成对不相交集的集合。Fork= 3，这个问题推广了经典的三维匹配问题，被列为卡普的原始21个NP完全问题之一。我们给出了一个3-集包装的近似因子为1.786的算法，改进了Neuwohner最近的最佳结果，我们的算法是基于Berman的局部搜索过程，试图提高平方权的总和，而不是问题的目标。当使用最大值为k的交换时，该算法获得的近似因子为。使用大小为k2（k-1）+k的交换，我们提供了一个相对简单的分析，以获得k = 3时的近似因子1.811。然后，我们表明，我们开发的工具可以适应更大的交换大小为2k 2（k- 1）+k给出一个近似因子为1.786。虽然我们主要关注的是casek= 3，但我们的方法实际上对allk> 3的因子给出了稍微更强的改进。在以前的作品中，我们的保证也适用于更一般的问题，找到一个最大的重量独立集（k+ 1）-爪自由图。
We consider the weightedk-set packing problem, in which we are given a collection of weighted sets, each with at mostkelements and must return a collection of pairwise disjoint sets with maximum total weight. Fork= 3, this problem generalizes the classical 3-dimensional matching problem listed as one of the Karp's original 21 NP-complete problems. We give an algorithm attaining an approximation factor of 1.786 for 3-set packing, improving on the recent best result of due to Neuwohner.Our algorithm is based on the local search procedure of Berman that attempts to improve the sum of squared weights rather than the problem's objective. When using exchanges of size at mostk, this algorithm attains an approximation factor of . Using exchanges of sizek2(k-1) +k, we provide a relatively simple analysis to obtain an approximation factor of 1.811 whenk= 3. We then show that the tools we develop can be adapted to larger exchanges of size 2k2(k— 1) +kto give an approximation factor of 1.786. Although our primary focus is on the casek= 3, our approach in fact gives slightly stronger improvements on the factor for allk> 3. As in previous works, our guarantees hold also for the more general problem of finding a maximum weight independent set in a (k+ 1)-claw free graph.