{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T16:01:41Z","timestamp":1774022501660,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T00:00:00Z","timestamp":1655337600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T00:00:00Z","timestamp":1655337600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"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"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1907937"],"award-info":[{"award-number":["CCF-1907937"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s10107-022-01842-3","type":"journal-article","created":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T11:03:09Z","timestamp":1655377389000},"page":"1093-1144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fixed parameter approximation scheme for min-max k-cut"],"prefix":"10.1007","volume":"197","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,6,16]]},"reference":[{"key":"1842_CR1","first-page":"13","volume-title":"Min-max correlation clustering via multicut","author":"S Ahmadi","year":"2019","unstructured":"Ahmadi, S., Khuller, S., Saha, B.: Min-max correlation clustering via multicut, pp. 13\u201326. Integer Programming and Comb. Optim, IPCO (2019)"},{"issue":"2","key":"1842_CR2","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-max graph partitioning and small set expansion. SIAM J. Comput. 43(2), 872\u2013904 (2014)","journal-title":"SIAM J. Comput."},{"key":"1842_CR3","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. Programming 183, 171\u2013193 (2020)","journal-title":"Math. Programming"},{"key":"1842_CR4","doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Chekuri, C.: Min-max partitioning of Hypergraphs and Symmetric Submodular Functions. In: Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1026\u20131038 (2021)","DOI":"10.1137\/1.9781611976465.64"},{"key":"1842_CR5","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 Comb. Optim, IPCO (2017)"},{"issue":"2","key":"1842_CR6","doi-asserted-by":"publisher","first-page":"1334","DOI":"10.1137\/19M1299359","volume":"34","author":"C Chekuri","year":"2020","unstructured":"Chekuri, C., Quanrud, K., Xu, C.: LP Relaxation and Tree Packing for Minimum $$k$$-Cut. SIAM J. Discrete Math. 34(2), 1334\u20131353 (2020)","journal-title":"SIAM J. Discrete Math."},{"key":"1842_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)"},{"key":"1842_CR8","unstructured":"Cygan, M., Komosa, P., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S., Wahlstrom, M.: Randomized contractions meet lean decompositions. arXiv: https:\/\/arxiv.org\/abs\/1810.06864 (2018)"},{"issue":"4","key":"1842_CR9","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":"1842_CR10","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S1571-0661(04)81014-4","volume":"78","author":"R Downey","year":"2003","unstructured":"Downey, R., Estivill-Castro, V., Fellows, M., Prieto, E., Rosamund, F.: Cutting up is hard to do: The parameterised complexity of k-cut and related problems. Electron. Notes Theor. Comput. Sci. 78, 209\u2013222 (2003)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"1842_CR11","doi-asserted-by":"crossref","unstructured":"Goldschmidt, O., Hochbaum, D.: Polynomial algorithm for the k-cut problem. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FOCS, pp. 444\u2013451 (1988)","DOI":"10.1109\/SFCS.1988.21960"},{"issue":"1","key":"1842_CR12","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.: A Polynomial Algorithm for the $$k$$-cut Problem for Fixed $$k$$. Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"1842_CR13","unstructured":"Gupta, A., Harris, D., Lee, E., Li, J.: Optimal Bounds for the $$k$$-cut Problem. arXiv:2005.08301 (2020)"},{"key":"1842_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: An FPT Algorithm Beating 2-Approximation for $$k$$-Cut. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2821\u20132837 (2018)","DOI":"10.1137\/1.9781611975031.179"},{"key":"1842_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: Faster exact and approximate algorithms for k-cut. In: Proceedings of the 59th IEEE annual Symposium on Foundations of Computer Science, FOCS, pp. 113\u2013123 (2018)","DOI":"10.1109\/FOCS.2018.00020"},{"key":"1842_CR16","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: The Karger-Stein Algorithm is Optimal for $$k$$-Cut. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, p. 473-484 (2020)","DOI":"10.1145\/3357713.3384285"},{"key":"1842_CR17","first-page":"9346","volume":"32","author":"S Kalhan","year":"2019","unstructured":"Kalhan, S., Makarychev, K., Zhou, T.: Correlation clustering with local objectives. Adv. Neural Inform. Process. Syst. 32, 9346\u20139355 (2019)","journal-title":"Adv. Neural Inform. Process. Syst."},{"issue":"2","key":"1842_CR18","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1287\/moor.24.2.383","volume":"24","author":"D Karger","year":"1999","unstructured":"Karger, D.: Random sampling in cut, flow, and network design problems. Math. Oper. Res. 24(2), 383\u2013413 (1999)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1842_CR19","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D Karger","year":"1996","unstructured":"Karger, D., Stein, C.: A new approach to the minimum cut problem. J. ACM 43(4), 601\u2013640 (1996)","journal-title":"J. ACM"},{"key":"1842_CR20","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K. I., Lin, B.: A nearly 5\/3-approximation FPT Algorithm for Min-$$k$$-Cut. In: Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 990\u2013999 (2020)","DOI":"10.1137\/1.9781611975994.59"},{"key":"1842_CR21","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1002\/net.3230030306","volume":"3","author":"E Lawler","year":"1973","unstructured":"Lawler, E.: Cutsets and Partitions of Hypergraphs. Networks 3, 275\u2013285 (1973)","journal-title":"Networks"},{"key":"1842_CR22","doi-asserted-by":"crossref","unstructured":"Li, J.: Faster minimum k-cut of a simple graph. In: Proceedings of the 60th Annual Symposium on Foundations of Computer Science, FOCS, pp. 1056\u20131077 (2019)","DOI":"10.1109\/FOCS.2019.00068"},{"key":"1842_CR23","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Saurabh, S., Surianarayanan, V.: A Parameterized Approximation Scheme for Min$$k$$-Cut. In: Proceedings of the 61st IEEE annual Symposium on Foundations of Computer Science, FOCS, pp. 798\u2013809 (2020)","DOI":"10.1109\/FOCS46700.2020.00079"},{"issue":"1","key":"1842_CR24","doi-asserted-by":"publisher","first-page":"10","DOI":"10.3390\/a11010010","volume":"11","author":"P Manurangsi","year":"2018","unstructured":"Manurangsi, P.: Inapproximability of Maximum Biclique Problems, Minimum $$k$$-Cut and Densest At-Least-$$k$$-Subgraph from the Small Set Expansion Hypothesis. Algorithms 11(1), 10 (2018)","journal-title":"Algorithms"},{"issue":"2","key":"1842_CR25","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1006\/jagm.1996.0047","volume":"21","author":"H Narayanan","year":"1996","unstructured":"Narayanan, H., Roy, S., Patkar, S.: Approximation algorithms for min-k-overlap problems using the principal lattice of partitions approach. J. Algorithms 21(2), 306\u2013330 (1996)","journal-title":"J. Algorithms"},{"issue":"1","key":"1842_CR26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.ejor.2007.01.040","volume":"186","author":"R Ravi","year":"2008","unstructured":"Ravi, R., Sinha, A.: Approximating k-cuts using network strength as a lagrangean relaxation. Eur. J. Oper. Res. 186(1), 77\u201390 (2008)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"1842_CR27","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.: Finding k Cuts within Twice the Optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J. Comput."},{"key":"1842_CR28","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"},{"key":"1842_CR29","doi-asserted-by":"crossref","unstructured":"Svitkina, Z., Tardos, \u00c9.: Min-max 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"},{"key":"1842_CR30","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Minimum $$k$$-way Cuts via Deterministic Greedy Tree Packing. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC, pp. 159\u2013166 (2008)","DOI":"10.1145\/1374376.1374402"},{"issue":"1","key":"1842_CR31","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10107-004-0510-2","volume":"102","author":"L Zhao","year":"2005","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: Greedy splitting algorithms for approximating multiway partition problems. Math. Programming 102(1), 167\u2013183 (2005)","journal-title":"Math. Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01842-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01842-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01842-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:20:38Z","timestamp":1675704038000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01842-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,16]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1842"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01842-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,16]]},"assertion":[{"value":"27 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}