Answers are grounded in this paper and cite their sources.
Weighted k-set packing asks for a maximum-weight collection of pairwise disjoint sets, each of cardinality at most k. For every fixed k∈ Z≥1, we give a polynomial-time algorithm with approximation factor (1- 1/√3 )k+O(log k) ≈ 0.4226k + O(log k), improving the previous best factor of 0.4621k + O(√k) 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.
No takes yet. Share an insight, caveat, or question.
Taziki et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: