{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:06Z","timestamp":1740109326947,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T00:00:00Z","timestamp":1653264000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T00:00:00Z","timestamp":1653264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1814613"],"award-info":[{"award-number":["CCF 1814613"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s00453-022-00983-3","type":"journal-article","created":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T19:05:35Z","timestamp":1653332735000},"page":"2667-2701","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["$$\\ell _p$$-Norm Multiway Cut"],"prefix":"10.1007","volume":"84","author":[{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0628-5532","authenticated-orcid":false,"given":"Weihang","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,23]]},"reference":[{"key":"983_CR1","first-page":"13","volume-title":"Min\u2013Max Correlation Clustering via Multicut","author":"S Ahmadi","year":"2019","unstructured":"Ahmadi, S., Khuller, S., Saha, B.: Min\u2013Max Correlation Clustering via Multicut, pp. 13\u201326. Integer Programming and Combinatorial Optimization, IPCO, Atlanta (2019)"},{"key":"983_CR2","first-page":"39","volume-title":"An Improved Integrality Gap for the C\u0103linescu\u2013Karloff\u2013Rabani Relaxation for Multiway Cut","author":"H Angelidakis","year":"2017","unstructured":"Angelidakis, H., Makarychev, Y., Manurangsi, P.: An Improved Integrality Gap for the C\u0103linescu\u2013Karloff\u2013Rabani Relaxation for Multiway Cut, pp. 39\u201350. Integer Programming and Combinatorial Optimization, IPCO, Atlanta (2017)"},{"issue":"2","key":"983_CR3","doi-asserted-by":"publisher","first-page":"872","DOI":"10.1137\/120873996","volume":"43","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J., Schwartz, R.: Min\u2013max graph partitioning and small set expansion. SIAM J. Comput. 43(2), 872\u2013904 (2014)","journal-title":"SIAM J. Comput."},{"key":"983_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s10107-020-01485-2","volume":"183","author":"K B\u00e9rczi","year":"2020","unstructured":"B\u00e9rczi, K., Chandrasekaran, K., Kir\u00e1ly, T., Madan, V.: Improving the integrality gap for multiway cut. Math. Program. 183, 171\u2013193 (2020)","journal-title":"Math. Program."},{"key":"983_CR5","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":"983_CR6","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.\u00a02400\u20132410 (2017)","DOI":"10.1137\/1.9781611974782.158"},{"issue":"3","key":"983_CR7","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."},{"key":"983_CR8","doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Chekuri, C.: Min\u2013max partitioning of hypergraphs and symmetric submodular functions. In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.\u00a01026\u20131038 (2021)","DOI":"10.1137\/1.9781611976465.64"},{"key":"983_CR9","first-page":"136","volume-title":"Local Guarantees in Graph Cuts and Clustering","author":"M Charikar","year":"2017","unstructured":"Charikar, M., Gupta, N., Schwartz, R.: Local Guarantees in Graph Cuts and Clustering, pp. 136\u2013147. Integer Programming and Combinatorial Optimization, IPCO, Atlanta (2017)"},{"key":"983_CR10","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Submodular cost allocation problem and applications. In: International Colloquium on Automata, Languages and Programming, ICALP, pp. 354\u2013366 (2011)","DOI":"10.1007\/978-3-642-22006-7_30"},{"issue":"1","key":"983_CR11","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."},{"key":"983_CR12","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/jgt.3190080106","volume":"8","author":"V Chv\u00e1tal","year":"1984","unstructured":"Chv\u00e1tal, V.: Recognizing decomposable graphs. J. Graph Theory 8, 51\u201353 (1984)","journal-title":"J. Graph Theory"},{"issue":"4","key":"983_CR13","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."},{"key":"983_CR14","series-title":"Series of Books in the Mathematical Sciences","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences, W.H. Freeman, San Francisco (1979)"},{"key":"983_CR15","first-page":"9346","volume":"32","author":"S Kalhan","year":"2019","unstructured":"Kalhan, S., Makarychev, K., Zhou, T.: Correlation clustering with local objectives. Adv. Neural Inf. Process. Syst. 32, 9346\u20139355 (2019)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"3","key":"983_CR16","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":"983_CR17","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.\u00a011\u201320 (2008)","DOI":"10.1145\/1374376.1374379"},{"issue":"3","key":"983_CR18","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"983_CR19","doi-asserted-by":"publisher","first-page":"4105","DOI":"10.1109\/TIT.2018.2819696","volume":"64","author":"G Puleo","year":"2018","unstructured":"Puleo, G., Milenkovic, O.: Correlation clustering and biclustering with locally bounded errors. IEEE Trans. Inf. Theory 64, 4105\u20134119 (2018)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"983_CR20","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: IEEE Conference on Computational Complexity, CCC, pp.\u00a064\u201373 (2012)","DOI":"10.1109\/CCC.2012.43"},{"key":"983_CR21","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.\u00a0724\u2013733 (2014)","DOI":"10.1145\/2591796.2591866"},{"key":"983_CR22","doi-asserted-by":"crossref","unstructured":"Svitkina, Z., Tardos, \u00c9.: Min\u2013max multiway cut. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX, pp. 207\u2013218 (2004)","DOI":"10.1007\/978-3-540-27821-4_19"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00983-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00983-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00983-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T14:16:23Z","timestamp":1660313783000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00983-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,23]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["983"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00983-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,5,23]]},"assertion":[{"value":"27 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}