The limits of local search for weighted k-set packing
研究了加权k-集打包问题，通过分析接近最优的实例，将无权重情形下的技术推广到加权情形，得到近似比渐近趋于k/2的算法，并证明局部搜索无法突破k/2的下界。
Abstract We consider the weighted k -set packing problem, where, given a collection $${\mathcal {S}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>S</mml:mi> </mml:math> of sets, each of cardinality at most k , and a positive weight function $$w:{\mathcal {S}}\rightarrow {\mathbb {Q}}_{>0}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>w</mml:mi> <mml:mo>:</mml:mo> <mml:mi>S</mml:mi> <mml:mo>→</mml:mo> <mml:msub> <mml:mi>Q</mml:mi> <mml:mrow> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> , the task is to find a sub-collection of $${\mathcal {S}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>S</mml:mi> </mml:math> consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time $$o(\frac{k}{\log k})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mi>k</mml:mi> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation unless $$P=NP$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>P</mml:mi> <mml:mo>=</mml:mo> <mml:mi>N</mml:mi> <mml:mi>P</mml:mi> </mml:mrow> </mml:math> (Hazan et al. in Comput Complex 15:20–39, 2006. https://doi.org/10.1007/s00037-006-0205-6 ), most previous approaches rely on local search. For twenty years, Berman’s algorithm SquareImp (Berman, in: Scandinavian workshop on algorithm theory, Springer, 2000. https://doi.org/10.1007/3-540-44985-X_19 ), which yields a polynomial-time $$\frac{k+1}{2}+\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mn>2</mml:mn> </mml:mfrac> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> -approximation for any fixed $$\epsilon >0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , has remained unchallenged. Only recently, it could be improved to $$\frac{k+1}{2}-\frac{1}{63,700,993}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mn>2</mml:mn> </mml:mfrac> <mml:mo>-</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mn>63</mml:mn> <mml:mo>,</mml:mo> <mml:mn>700</mml:mn> <mml:mo>,</mml:mo> <mml:mn>993</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:math> by Neuwohner (38th International symposium on theoretical aspects of computer science (STACS 2021), Leibniz international proceedings in informatics (LIPIcs), 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.53 ). In her paper, she showed that instances for which the analysis of SquareImp is almost tight are “close to unweighted” in a certain sense. But for the unit weight variant, the best known approximation guarantee is $$\frac{k+1}{3}+\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mn>3</mml:mn> </mml:mfrac> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> (Fürer and Yu in International symposium on combinatorial optimization, Springer, 2014. https://doi.org/10.1007/978-3-319-09174-7_35 ). Using this observation as a starting point, we conduct a more in-depth analysis of close-to-tight instances of SquareImp. This finally allows us to generalize techniques used in the unweighted case to the weighted setting. In doing so, we obtain approximation guarantees of $$\frac{k+\epsilon _k}{2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:mrow> <mml:mn>2</mml:mn> </mml:mfrac> </mml:math> , where $$\lim _{k\rightarrow \infty } \epsilon _k = 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>lim</mml:mo> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:msub> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> . On the other hand, we prove that this is asymptotically best possible in that local improvements of logarithmically bounded size cannot produce an approximation ratio below $$\frac{k}{2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:mfrac> </mml:math> .