{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:11:04Z","timestamp":1760015464874},"publisher-location":"Cham","reference-count":10,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_4","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:04:39Z","timestamp":1495544679000},"page":"39-50","source":"Crossref","is-referenced-by-count":8,"title":["An Improved Integrality Gap for the C\u0103linescu-Karloff-Rabani Relaxation for Multiway Cut"],"prefix":"10.1007","author":[{"given":"Haris","family":"Angelidakis","sequence":"first","affiliation":[]},{"given":"Yury","family":"Makarychev","sequence":"additional","affiliation":[]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"4_CR1","unstructured":"Angelidakis, H., Makarychev, Y., Manurangsi, P.: An improved integrality gap for the Calinescu-Karloff-Rabani relaxation for multiway cut. CoRR abs\/1611.05530 (2016). http:\/\/arxiv.org\/abs\/1611.05530"},{"key":"4_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 45th ACM Symposium on Theory of Computing, STOC, pp. 535\u2013544 (2013)","DOI":"10.1145\/2488608.2488675"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Schwartz, R., Weizman, B.: Simplex transformations and the multiway cut problem. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2400\u20132410 (2017)","DOI":"10.1137\/1.9781611974782.158"},{"issue":"3","key":"4_CR4","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H.J., Rabani, Y.: An improved approximation algorithm for multiway cut. J. Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-48777-8_9","volume-title":"Integer Programming and Combinatorial Optimization","author":"WH Cunningham","year":"1999","unstructured":"Cunningham, W.H., Tang, L.: Optimal 3-terminal cuts and linear programming. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, pp. 114\u2013125. Springer, Heidelberg (1999). doi: 10.1007\/3-540-48777-8_9"},{"issue":"4","key":"4_CR6","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"4_CR7","doi-asserted-by":"crossref","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 + \\frac{1}{k - 1})$$ on the integrality ratio of the C\u0103linescu-Karloff-Rabani relaxation for multiway cut. Inf. Process. Lett. 75(1\u20132), 43\u201350 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"4_CR8","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"DR Karger","year":"2004","unstructured":"Karger, D.R., Klein, P.N., Stein, C., Thorup, M., Young, N.E.: Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res. 29(3), 436\u2013461 (2004)","journal-title":"Math. Oper. Res."},{"key":"4_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 40th ACM Symposium on Theory of Computing, STOC, pp. 11\u201320 (2008)","DOI":"10.1145\/1374376.1374379"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Sharma, A., Vondr\u00e1k, J.: Multiway cut, pairwise realizable distributions, and descending thresholds. In: Proceedings of the 46th ACM Symposium on Theory of Computing, STOC, pp. 724\u2013733 (2014)","DOI":"10.1145\/2591796.2591866"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T23:49:42Z","timestamp":1569368982000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}