{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:29Z","timestamp":1750694789708,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031069000"},{"type":"electronic","value":"9783031069017"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-06901-7_31","type":"book-chapter","created":{"date-parts":[[2022,5,27]],"date-time":"2022-05-27T00:22:30Z","timestamp":1653610950000},"page":"415-428","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Limits of\u00a0Local Search for\u00a0Weighted k-Set Packing"],"prefix":"10.1007","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":[[2022,5,27]]},"reference":[{"issue":"3","key":"31_CR1","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":"31_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/3-540-44985-X_19","volume-title":"Algorithm Theory - SWAT 2000","author":"P Berman","year":"2000","unstructured":"Berman, P.: A d\/2 approximation for maximum weight independent set in d-claw free graphs. In: SWAT 2000. LNCS, vol. 1851, pp. 214\u2013219. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44985-X_19"},{"key":"31_CR3","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":"31_CR4","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":"31_CR5","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, Berkeley, CA, USA, 26\u201329 October 2013, pp. 509\u2013518. IEEE Computer Society (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.61","DOI":"10.1109\/FOCS.2013.61"},{"key":"31_CR6","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":"31_CR7","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."},{"key":"31_CR8","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)"},{"key":"31_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-319-09174-7_35","volume-title":"Combinatorial Optimization","author":"M F\u00fcrer","year":"2014","unstructured":"F\u00fcrer, M., Yu, H.: Approximating the $$k$$-set packing problem by local improvements. In: Fouilhoux, P., Gouveia, L.E.N., Mahjoub, A.R., Paschos, V.T. (eds.) ISCO 2014. LNCS, vol. 8596, pp. 408\u2013420. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09174-7_35"},{"key":"31_CR10","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 (1995). https:\/\/dl.acm.org\/doi\/10.5555\/313651.313687"},{"key":"31_CR11","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":"31_CR12","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. Disc. Math. 2(1), 68\u201372 (1989). https:\/\/doi.org\/10.1137\/0402008","journal-title":"SIAM J. Disc. Math."},{"key":"31_CR13","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems. In: Complexity of computer computations, pp. 85\u2013103. Springer, Heidelberg (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"31_CR14","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. Comb. Theory Ser. B 28(3), 284\u2013304 (1980). https:\/\/doi.org\/10.1016\/0095-8956(80)90074-X","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"31_CR15","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. Jpn. 44(2), 194\u2013204 (2001). https:\/\/doi.org\/10.15807\/jorsj.44.194","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"31_CR16","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":"31_CR17","unstructured":"Neuwohner, M.: The limits of local search for the maximum weight independent set problem in d-claw free graphs (2021). https:\/\/arxiv.org\/abs\/2106.03555"},{"issue":"1","key":"31_CR18","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. Disc. Math. 29(1), 53\u201376 (1980). https:\/\/doi.org\/10.1016\/0012-365X(90)90287-R","journal-title":"Disc. Math."},{"key":"31_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1007\/978-3-642-39206-1_67","volume-title":"Automata, Languages, and Programming","author":"M Sviridenko","year":"2013","unstructured":"Sviridenko, M., Ward, J.: Large neighborhood local search for the maximum set packing problem. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 792\u2013803. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_67"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-06901-7_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T23:05:02Z","timestamp":1653951902000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-06901-7_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031069000","9783031069017"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-06901-7_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"27 May 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Eindhoven","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.ipco2022.com\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"93","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}