← 研踪 PaperTrailarXiv:2611.20724 · v1
Improved Approximation for Weighted $k$-Set Packing via a Simple Two-Phase Approach
首次提交 2026-11-16 16:30
版本更新 2026-11-16 16:30
雷达观测 2026-11-17 13:07
摘要
Weighted -set packing asks for a maximum-weight collection of pairwise disjoint sets, each of cardinality at most . For every fixed , we give a polynomial-time algorithm with approximation factor , improving the previous best factor of through a simple two-phase approach. In a first phase, our algorithm constructs a packing by processing random weight buckets of varying widths with an unweighted packing algorithm. We show that a small expected weight of this packing relative to the optimum forces a large expected total surplus in the optimum. Surplus quantifies the potential for improving a packing through star swaps. In the second phase, we solve and round a configuration LP to turn sufficiently large surplus into an increase in expected weight. Our procedure can easily be derandomized.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-16 16:30 · 最新观测版本
Improved Approximation for Weighted $k$-Set Packing via a Simple Two-Phase Approach
Weighted -set packing asks for a maximum-weight collection of pairwise disjoint sets, each of cardinality at most . For every fixed , we give a polynomial-time algorithm with approximation factor , improving the previous best factor of through a simple two-phase approach. In a first phase, our algorithm constructs a packing by processing random weight buckets of varying widths with an unweighted packing algorithm. We show that a small expected weight of this packing relative to the optimum forces a large expected total surplus in the optimum. Surplus quantifies the potential for improving a packing through star swaps. In the second phase, we solve and round a configuration LP to turn sufficiently large surplus into an increase in expected weight. Our procedure can easily be derandomized.
查看此版本解读 →查看此版本原文 ↗