{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T06:28:57Z","timestamp":1769236137553,"version":"3.49.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T00:00:00Z","timestamp":1698451200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T00:00:00Z","timestamp":1698451200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008131","name":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008131","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"abstract":"Abstract<\/jats:title>We consider the weighted k<\/jats:italic>-set packing problem, where, given a collection $${\\mathcal {S}}$$<\/jats:tex-math>\n S<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of sets, each of cardinality at most k<\/jats:italic>, and a positive weight function $$w:{\\mathcal {S}}\\rightarrow {\\mathbb {Q}}_{>0}$$<\/jats:tex-math>\n \n w<\/mml:mi>\n :<\/mml:mo>\n S<\/mml:mi>\n \u2192<\/mml:mo>\n \n Q<\/mml:mi>\n \n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the task is to find a sub-collection of $${\\mathcal {S}}$$<\/jats:tex-math>\n S<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time $$o(\\frac{k}{\\log k})$$<\/jats:tex-math>\n \n o<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n \n log<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation unless $$P=NP$$<\/jats:tex-math>\n \n P<\/mml:mi>\n =<\/mml:mo>\n N<\/mml:mi>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (Hazan et al. in Comput Complex 15:20\u201339, 2006. https:\/\/doi.org\/10.1007\/s00037-006-0205-6<\/jats:ext-link>), most previous approaches rely on local search. For twenty years, Berman\u2019s algorithm SquareImp<\/jats:italic> (Berman, in: Scandinavian workshop on algorithm theory, Springer, 2000. https:\/\/doi.org\/10.1007\/3-540-44985-X_19<\/jats:ext-link>), which yields a polynomial-time $$\\frac{k+1}{2}+\\epsilon $$<\/jats:tex-math>\n \n \n \n k<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mfrac>\n +<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for any fixed $$\\epsilon >0$$<\/jats:tex-math>\n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, has remained unchallenged. Only recently, it could be improved to $$\\frac{k+1}{2}-\\frac{1}{63,700,993}$$<\/jats:tex-math>\n \n \n \n k<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mfrac>\n -<\/mml:mo>\n \n 1<\/mml:mn>\n \n 63<\/mml:mn>\n ,<\/mml:mo>\n 700<\/mml:mn>\n ,<\/mml:mo>\n 993<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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<\/jats:ext-link>). In her paper, she showed that instances for which the analysis of SquareImp is almost tight are \u201cclose to unweighted\u201d in a certain sense. But for the unit weight variant, the best known approximation guarantee is $$\\frac{k+1}{3}+\\epsilon $$<\/jats:tex-math>\n \n \n \n k<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:mfrac>\n +<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (F\u00fcrer and Yu in International symposium on combinatorial optimization, Springer, 2014. https:\/\/doi.org\/10.1007\/978-3-319-09174-7_35<\/jats:ext-link>). 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}$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n +<\/mml:mo>\n \n \u03f5<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$\\lim _{k\\rightarrow \\infty } \\epsilon _k = 0$$<\/jats:tex-math>\n \n \n lim<\/mml:mo>\n \n k<\/mml:mi>\n \u2192<\/mml:mo>\n \u221e<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n \u03f5<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n =<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. 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\u00a0$$\\frac{k}{2}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10107-023-02026-3","type":"journal-article","created":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T06:02:58Z","timestamp":1698472978000},"page":"389-427","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The limits of local search for weighted k-set packing"],"prefix":"10.1007","volume":"206","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3664-3687","authenticated-orcid":false,"given":"Meike","family":"Neuwohner","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,28]]},"reference":[{"issue":"4","key":"2026_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995). https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"J. ACM"},{"issue":"3","key":"2026_CR2","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1287\/moor.23.3.640","volume":"23","author":"EM Arkin","year":"1998","unstructured":"Arkin, E.M., Hassin, R.: On local search for weighted $$k$$-set packing. Math. Oper. Res. 23(3), 640\u2013648 (1998). https:\/\/doi.org\/10.1287\/moor.23.3.640","journal-title":"Math. Oper. Res."},{"key":"2026_CR3","doi-asserted-by":"publisher","unstructured":"Berman, P.: A $$d\/2$$ approximation for maximum weight independent set in $$d$$-claw free graphs. In: Scandinavian Workshop on Algorithm Theory, pp. 214\u2013219. Springer (2000). https:\/\/doi.org\/10.1007\/3-540-44985-X_19","DOI":"10.1007\/3-540-44985-X_19"},{"key":"2026_CR4","unstructured":"Berman, P., F\u00fcrer, M.: Approximating maximum independent set in bounded degree graphs. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 365\u2013371 (1994). https:\/\/dl.acm.org\/doi\/pdf\/10.5555\/314464.314570"},{"issue":"2","key":"2026_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1006\/jagm.2000.1155","volume":"39","author":"B Chandra","year":"2001","unstructured":"Chandra, B., Halld\u00f3rsson, M.M.: Greedy local improvement and weighted set packing approximation. J. Algorithms 39(2), 223\u2013240 (2001). https:\/\/doi.org\/10.1006\/jagm.2000.1155","journal-title":"J. Algorithms"},{"key":"2026_CR6","doi-asserted-by":"publisher","unstructured":"Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26\u201329 October, 2013, Berkeley, CA, USA, pp. 509\u2013518. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.61","DOI":"10.1109\/FOCS.2013.61"},{"key":"2026_CR7","doi-asserted-by":"publisher","unstructured":"Cygan, M., Grandoni, F., Mastrolilli, M.: How to sell hyperedges: the hypermatching assignment problem. In: Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 342\u2013351. SIAM (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.25","DOI":"10.1137\/1.9781611973105.25"},{"key":"2026_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069b.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bureau Stand. Sect. B Math. Math. Phys. 69B, 125\u2013130 (1965). https:\/\/doi.org\/10.6028\/jres.069b.013","journal-title":"J. Res. Natl. Bureau Stand. Sect. B Math. Math. Phys."},{"issue":"3","key":"2026_CR9","first-page":"251","volume":"12","author":"P Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P., Sachs, H.: Regul\u00e4re Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 12(3), 251\u2013257 (1963)","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"key":"2026_CR10","doi-asserted-by":"publisher","unstructured":"F\u00fcrer, M., Yu, H.: Approximating the $$k$$-set packing problem by local improvements. In: International Symposium on Combinatorial Optimization, pp. 408\u2013420. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-09174-7_35","DOI":"10.1007\/978-3-319-09174-7_35"},{"key":"2026_CR11","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 160\u2013169. Society for Industrial and Applied Mathematics, USA (1995). https:\/\/dl.acm.org\/doi\/10.5555\/313651.313687"},{"key":"2026_CR12","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E Hazan","year":"2006","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating $$k$$-Set Packing. Comput. Complex. 15, 20\u201339 (2006). https:\/\/doi.org\/10.1007\/s00037-006-0205-6","journal-title":"Comput. Complex."},{"issue":"1","key":"2026_CR13","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"CAJ Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every $$t$$ of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68\u201372 (1989). https:\/\/doi.org\/10.1137\/0402008","journal-title":"SIAM J. Discrete Math."},{"key":"2026_CR14","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations. Plenum Press (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"2026_CR15","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Combin. Theory Ser. B 28(3), 284\u2013304 (1980). https:\/\/doi.org\/10.1016\/0095-8956(80)90074-X","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"2026_CR16","doi-asserted-by":"publisher","first-page":"194","DOI":"10.15807\/jorsj.44.194","volume":"44","author":"D Nakamura","year":"2001","unstructured":"Nakamura, D., Tamura, A.: A revision of Minty\u2019s algorithm for finding a maximum weight stable set of a claw-free graph. J. Oper. Res. Soc. Japan 44(2), 194\u2013204 (2001). https:\/\/doi.org\/10.15807\/jorsj.44.194","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"2026_CR17","doi-asserted-by":"publisher","unstructured":"Neuwohner, M.: An improved approximation algorithm for the maximum weight independent set problem in d-claw free graphs. In: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Leibniz International Proceedings in Informatics (LIPIcs), vol. 187, pp. 53:1\u201353:20 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.53","DOI":"10.4230\/LIPIcs.STACS.2021.53"},{"key":"2026_CR18","doi-asserted-by":"publisher","unstructured":"Neuwohner, M.: The limits of local search for weighted k-set packing. In: Aardal, K., Sanit\u00e0, L. (eds.) Integer Programming and Combinatorial Optimization\u201423rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27\u201329, 2022, Proceedings, Lecture Notes in Computer Science, vol. 13265, pp. 415\u2013428. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-06901-7_31","DOI":"10.1007\/978-3-031-06901-7_31"},{"issue":"1","key":"2026_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi, N.: Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discrete Math. 29(1), 53\u201376 (1980). https:\/\/doi.org\/10.1016\/0012-365X(90)90287-R","journal-title":"Discrete Math."},{"issue":"5","key":"2026_CR20","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"JP Schmidt","year":"1990","unstructured":"Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775\u2013786 (1990). https:\/\/doi.org\/10.1137\/0219054","journal-title":"SIAM J. Comput."},{"key":"2026_CR21","doi-asserted-by":"publisher","unstructured":"Sviridenko, M., Ward, J.: Large neighborhood local search for the maximum set packing problem. In: International Colloquium on Automata, Languages, and Programming, pp. 792\u2013803. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_67","DOI":"10.1007\/978-3-642-39206-1_67"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02026-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02026-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02026-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T12:23:34Z","timestamp":1721823814000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02026-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,28]]},"references-count":21,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["2026"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02026-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,28]]},"assertion":[{"value":"5 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}