{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:49:35Z","timestamp":1742917775936,"version":"3.40.3"},"publisher-location":"Cham","reference-count":12,"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_23","type":"book-chapter","created":{"date-parts":[[2022,5,27]],"date-time":"2022-05-27T00:22:30Z","timestamp":1653610950000},"page":"305-318","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Matroid-Based TSP Rounding for Half-Integral Solutions"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Jason","family":"Li","sequence":"additional","affiliation":[]},{"given":"Marcin","family":"Mucha","sequence":"additional","affiliation":[]},{"given":"Heather","family":"Newman","sequence":"additional","affiliation":[]},{"given":"Sherry","family":"Sarkar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,27]]},"reference":[{"unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 338, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh (1976)","key":"23_CR1"},{"unstructured":"Fleiner, T., Frank, A.: A quick proof for the cactus representation of mincuts. Technical report Quick-proof No. 2009\u201303, EGRES (2009)","key":"23_CR2"},{"doi-asserted-by":"publisher","unstructured":"Haddadan, A., Newman, A.: Towards improving Christofides algorithm for half-integer TSP. In: ESA, pp. 56:1\u201356:12 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.56","key":"23_CR3","DOI":"10.4230\/LIPIcs.ESA.2019.56"},{"issue":"3","key":"23_CR4","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1214\/aoms\/1177728178","volume":"27","author":"W Hoeffding","year":"1956","unstructured":"Hoeffding, W.: On the distribution of the number of successes in independent trials. Ann. Math. Stat. 27(3), 713\u2013721 (1956)","journal-title":"Ann. Math. Stat."},{"unstructured":"Karlin, A., Klein, N., Oveis Gharan, S.: A (slightly) improved bound on the integrality gap of the subtour LP for TSP. CoRR abs\/2105.10043 (2021). https:\/\/arxiv.org\/abs\/2105.10043","key":"23_CR5"},{"doi-asserted-by":"publisher","unstructured":"Karlin, A.R., Klein, N., Oveis Gharan, S.: An improved approximation algorithm for TSP in the half integral case. In: STOC, pp. 28\u201339. ACM (2020). https:\/\/doi.org\/10.1145\/3357713.3384273","key":"23_CR6","DOI":"10.1145\/3357713.3384273"},{"unstructured":"Karlin, A.R., Klein, N., Oveis Gharan, S.: A (slightly) improved approximation algorithm for metric TSP. CoRR abs\/2007.01409 (2020). https:\/\/arxiv.org\/abs\/2007.01409","key":"23_CR7"},{"doi-asserted-by":"publisher","unstructured":"Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: FOCS, pp. 550\u2013559 (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.80","key":"23_CR8","DOI":"10.1109\/FOCS.2011.80"},{"doi-asserted-by":"publisher","unstructured":"Schalekamp, F., Williamson, D.P., van Zuylen, A.: 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the boyd-carr conjecture. Math. Oper. Res. 39(2), 403\u2013417 (2014). https:\/\/doi.org\/10.1287\/moor.2013.0608","key":"23_CR9","DOI":"10.1287\/moor.2013.0608"},{"unstructured":"Serdyukov, A.: O nekotorykh ekstremal\u2019nykh obkhodakh v grafakh. Upravlyaemye sistemy, 17, 76\u201379 (1978). http:\/\/nas1.math.nsc.ru\/aim\/journals\/us\/us17\/us17_007.pdf","key":"23_CR10"},{"issue":"6","key":"23_CR11","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"DB Shmoys","year":"1990","unstructured":"Shmoys, D.B., Williamson, D.P.: Analyzing the Held-Karp TSP bound: a monotonicity property with application. Info. Proc. Let. 35(6), 281\u2013285 (1990)","journal-title":"Info. Proc. Let."},{"doi-asserted-by":"publisher","unstructured":"Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. In: Combinatorial Optimization II, Mathematical Programming Studies, vol. 13, pp. 121\u2013134. Springer (1980). https:\/\/doi.org\/10.1007\/BFb0120913","key":"23_CR12","DOI":"10.1007\/BFb0120913"}],"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_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T23:03:59Z","timestamp":1653951839000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-06901-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031069000","9783031069017"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-06901-7_23","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)"}}]}}