{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:04Z","timestamp":1781078284740,"version":"3.54.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,3,6]],"date-time":"2020-03-06T00:00:00Z","timestamp":1583452800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,6]],"date-time":"2020-03-06T00:00:00Z","timestamp":1583452800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"New National Excellence Program of the Ministry of Human Capacities","award":["UNKP-18-4"],"award-info":[{"award-number":["UNKP-18-4"]}]},{"name":"Hungarian National Research, Development and Innovation O?ce","award":["NKFIH grant K120254"],"award-info":[{"award-number":["NKFIH grant K120254"]}]},{"name":"NSF","award":["CCF-1319376"],"award-info":[{"award-number":["CCF-1319376"]}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-1907937"],"award-info":[{"award-number":["CCF-1907937"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-1814613"],"award-info":[{"award-number":["CCF-1814613"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s10107-020-01485-2","type":"journal-article","created":{"date-parts":[[2020,3,6]],"date-time":"2020-03-06T17:02:31Z","timestamp":1583514151000},"page":"171-193","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Improving the integrality gap for multiway cut"],"prefix":"10.1007","volume":"183","author":[{"given":"Krist\u00f3f","family":"B\u00e9rczi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tam\u00e1s","family":"Kir\u00e1ly","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vivek","family":"Madan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,3,6]]},"reference":[{"key":"1485_CR1","doi-asserted-by":"crossref","unstructured":"Angelidakis, H., Makarychev, Y., Manurangsi, P.: An improved integrality gap for the C\u0103linescu\u2013Karloff\u2013Rabani relaxation for multiway cut. In: Integer Programming and Combinatorial Optimization, IPCO, pp. 39\u201350 (2017)","DOI":"10.1007\/978-3-319-59250-3_4"},{"key":"1485_CR2","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J., Schwartz, R.: Simplex partitioning via exponential clocks and the multiway cut problem. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC, pp. 535\u2013544 (2013)","DOI":"10.1145\/2488608.2488675"},{"key":"1485_CR3","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Schwartz, R., Weizman, B.: Simplex transformations and the multiway cut problem. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2400\u20132410 (2017)","DOI":"10.1137\/1.9781611974782.158"},{"issue":"3","key":"1485_CR4","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. J. Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1485_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-005-0668-2","volume":"106","author":"K Cheung","year":"2006","unstructured":"Cheung, K., Cunningham, W., Tang, L.: Optimal 3-terminal cuts and linear programming. Math. Program. 106(1), 1\u201323 (2006)","journal-title":"Math. Program."},{"issue":"4","key":"1485_CR6","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1485_CR7","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0020-0190(00)00065-X","volume":"75","author":"A Freund","year":"2000","unstructured":"Freund, A., Karloff, H.: A lower bound of 8\/(7+1\/(k-1)) on the integrality ratio of the C\u0103linescu\u2013Karloff\u2013Rabani relaxation for multiway cut. Inf. Process. Lett. 75(1), 43\u201350 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1485_CR8","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"D Karger","year":"2004","unstructured":"Karger, D., Klein, P., Stein, C., Thorup, M., Young, N.: Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res. 29(3), 436\u2013461 (2004)","journal-title":"Math. Oper. Res."},{"key":"1485_CR9","doi-asserted-by":"crossref","unstructured":"Manokaran, R., Naor, J., Raghavendra, P., Schwartz, R.: SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC, pp. 11\u201320 (2008)","DOI":"10.1145\/1374376.1374379"},{"key":"1485_CR10","doi-asserted-by":"crossref","unstructured":"Mirzakhani, M., Vondr\u00e1k, J.: Sperner\u2019s colorings, hypergraph labeling problems and fair division. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 873\u2013886 (2015)","DOI":"10.1137\/1.9781611973730.60"},{"key":"1485_CR11","doi-asserted-by":"crossref","unstructured":"Sharma, A., Vondr\u00e1k, J.: Multiway cut, pairwise realizable distributions, and descending thresholds. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC, pp. 724\u2013733 (2014)","DOI":"10.1145\/2591796.2591866"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01485-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-020-01485-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01485-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T00:32:56Z","timestamp":1614990776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-020-01485-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,6]]},"references-count":11,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1485"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01485-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,6]]},"assertion":[{"value":"15 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}