{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,17]],"date-time":"2026-05-17T10:15:32Z","timestamp":1779012932269,"version":"3.51.4"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,11,13]],"date-time":"2019-11-13T00:00:00Z","timestamp":1573603200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,13]],"date-time":"2019-11-13T00:00:00Z","timestamp":1573603200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1526799"],"award-info":[{"award-number":["CCF-1526799"]}],"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-1319376"],"award-info":[{"award-number":["CCF-1319376"]}],"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":[[2021,3]]},"DOI":"10.1007\/s10107-019-01443-7","type":"journal-article","created":{"date-parts":[[2019,11,13]],"date-time":"2019-11-13T13:21:56Z","timestamp":1573651316000},"page":"85-113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Hypergraph k-cut in randomized polynomial time"],"prefix":"10.1007","volume":"186","author":[{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chao","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6323-3755","authenticated-orcid":false,"given":"Xilin","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,13]]},"reference":[{"issue":"1\u20132","key":"1443_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-9260(95)00008-4","volume":"19","author":"C Alpert","year":"1995","unstructured":"Alpert, C., Kahng, A.: Recent developments in netlist partitioning: a survey. Integr. VLSI J. 19(1\u20132), 1\u201381 (1995)","journal-title":"Integr. VLSI J."},{"key":"1443_CR2","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an $$o(n^{\\frac{1}{4}})$$ approximation for densest $$k$$-subgraph. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, STOC \u201910, pp.\u00a0201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"1443_CR3","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Approximation algorithms for submodular multiway partition. In: Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science, FOCS \u201911, pp.\u00a0807\u2013816 (2011)","DOI":"10.1109\/FOCS.2011.34"},{"key":"1443_CR4","unstructured":"Chekuri, C., Li, S.: A note on the hardness of approximating the $$k$$-way hypergraph cut problem, Manuscript, http:\/\/chekuri.cs.illinois.edu\/papers\/hypergraph-kcut.pdf (2015)"},{"key":"1443_CR5","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Xu, C.: Computing minimum cuts in hypergraphs. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201917, pp.\u00a01085\u20131100 (2017)","DOI":"10.1137\/1.9781611974782.70"},{"key":"1443_CR6","unstructured":"Chekuri, Chandra, Quanrud, Kent, Xu, Chao.: LP relaxation and tree packing for minimum $$k$$-cuts. In: 2nd Symposium on Simplicity in Algorithms (SOSA 2019), pp.\u00a07:1\u20137:18 (2019)"},{"key":"1443_CR7","doi-asserted-by":"crossref","unstructured":"Coudert, D., Datta, P., Perennes, S., Rivano, H., Voge, M.-E.: Shared Risk Resource Group: Complexity and Approximability Issues, Research Report RR-5859, INRIA (2006)","DOI":"10.1142\/S0129626407002958"},{"issue":"4","key":"1443_CR8","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.disopt.2013.10.002","volume":"10","author":"T Fukunaga","year":"2013","unstructured":"Fukunaga, T.: Computing minimum multiway cuts in hypergraphs. Discrete Optim. 10(4), 371\u2013382 (2013)","journal-title":"Discrete Optim."},{"key":"1443_CR9","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Karger, D., Panigrahi, D.: Random Contractions and Sampling for Hypergraph and Hedge Connectivity. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201917, pp.\u00a01101\u20131114 (2017)","DOI":"10.1137\/1.9781611974782.71"},{"issue":"1","key":"1443_CR10","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":"1443_CR11","unstructured":"Gui\u00f1ez, F., Queyranne, M.: The size-constrained submodular $$k$$-partition problem, Manuscript, https:\/\/docs.google.com\/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxmbGF2aW9ndWluZXpob21lcGFnZXxneDo0NDVlMThkMDg4ZWRlOGI1 (2012)"},{"key":"1443_CR12","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, pp.\u00a02821\u20132837 (2018)","DOI":"10.1137\/1.9781611975031.179"},{"key":"1443_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, Anupam, Lee, Euiwoong, Li, Jason.: Faster exact and approximate algorithms for k-cut. In: Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS \u201918, pp.\u00a0113\u2013123 (2018)","DOI":"10.1109\/FOCS.2018.00020"},{"key":"1443_CR14","volume-title":"Inequalities","author":"G Hardy","year":"1952","unstructured":"Hardy, G., Littlewood, J., P\u00f3lya, G.: Inequalities, 2nd edn. Cambridge University Press, Cambridge (1952)","edition":"2"},{"issue":"2","key":"1443_CR15","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/s00453-001-0070-2","volume":"32","author":"Y Kamidoi","year":"2002","unstructured":"Kamidoi, Y., Wakabayashi, S., Yoshida, N.: A divide-and-conquer approach to the minimum $$k$$-way cut problem. Algorithmica 32(2), 262\u2013276 (2002)","journal-title":"Algorithmica"},{"issue":"5","key":"1443_CR16","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1137\/050631616","volume":"36","author":"Y Kamidoi","year":"2007","unstructured":"Kamidoi, Y., Yoshida, N., Nagamochi, H.: A deterministic algorithm for finding all minimum $$k$$-way cuts. SIAM J. Comput. 36(5), 1329\u20131341 (2007)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1443_CR17","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":"1443_CR18","unstructured":"Klimmek, R., Wagner, F.: A simple hypergraph min cut algorithm. Internal Report B 96-02 Bericht FU Berlin Fachbereich Mathematik und Informatik (1995)"},{"key":"1443_CR19","doi-asserted-by":"crossref","unstructured":"Kogan, D., Krauthgamer, R.: Sketching cuts in graphs and hypergraphs. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS\u201915, pp.\u00a0367\u2013376 (2015)","DOI":"10.1145\/2688073.2688093"},{"key":"1443_CR20","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"},{"issue":"1","key":"1443_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-9260(00)00008-0","volume":"30","author":"W-K Mak","year":"2000","unstructured":"Mak, W.-K., Wong, D.: A fast hypergraph min-cut algorithm for circuit partitioning. Integr. VLSI J. 30(1), 1\u201311 (2000)","journal-title":"Integr. VLSI J."},{"key":"1443_CR22","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest $$k$$-subgraph. In: Proceedings of the 49th Annual ACM Symposium on Theory of Computing, STOC\u201917, pp.\u00a0954\u2013961 (2017)","DOI":"10.1145\/3055399.3055412"},{"key":"1443_CR23","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Inapproximability of maximum Biclique problems, minimum $$k$$-cut and densest at-least-$$k$$-subgraph from the small set expansion hypothesis. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP\u201917, pp.\u00a079:1\u201379:14 (2017)","DOI":"10.3390\/a11010010"},{"issue":"3","key":"1443_CR24","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1007\/s00453-010-9483-0","volume":"62","author":"K Okumoto","year":"2012","unstructured":"Okumoto, K., Fukunaga, T., Nagamochi, H.: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica 62(3), 787\u2013806 (2012)","journal-title":"Algorithmica"},{"key":"1443_CR25","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, STOC\u201910, pp.\u00a0755\u2013764 (2010)","DOI":"10.1145\/1806689.1806792"},{"issue":"1","key":"1443_CR26","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":"1443_CR27","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\u201908, pp.\u00a0159\u2013166 (2008)","DOI":"10.1145\/1374376.1374402"},{"key":"1443_CR28","doi-asserted-by":"crossref","unstructured":"Xiao, M.: An improved divide-and-conquer algorithm for finding all minimum k-way cuts. In: Proceedings of 19th International Symposium on Algorithms and Computation, ISAAC\u201908, pp.\u00a0208\u2013219 (2008)","DOI":"10.1007\/978-3-540-92182-0_21"},{"issue":"14","key":"1443_CR29","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1016\/j.ipl.2010.05.003","volume":"110","author":"M Xiao","year":"2010","unstructured":"Xiao, M.: Finding minimum 3-way cuts in hypergraphs. Inf. Process. Lett. (Preliminary version in TAMC 2008) 110(14), 554\u2013558 (2010)","journal-title":"Inf. Process. Lett. (Preliminary version in TAMC 2008)"},{"issue":"2","key":"1443_CR30","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/s10878-009-9222-0","volume":"21","author":"P Zhang","year":"2011","unstructured":"Zhang, P., Cai, J.-Y., Tang, L.-Q., Zhao, W.-B.: Approximation and hardness results for label cut and related problems. J. Comb. Optim. 21(2), 192\u2013208 (2011)","journal-title":"J. Comb. Optim."},{"key":"1443_CR31","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2016.08.006","volume":"648","author":"P Zhang","year":"2016","unstructured":"Zhang, P., Fu, B.: The label cut problem with respect to path length and label frequency. Theor. Comput. Sci. 648, 72\u201383 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"1443_CR32","unstructured":"Zhao, L.: Approximation algorithms for partition and design problems in networks. Ph.D. thesisGraduate School of Informatics, Kyoto University, Japan (2002)"},{"issue":"1","key":"1443_CR33","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. Program. 102(1), 167\u2013183 (2005)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01443-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01443-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01443-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,4]],"date-time":"2022-10-04T22:34:33Z","timestamp":1664922873000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01443-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,13]]},"references-count":33,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["1443"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01443-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,13]]},"assertion":[{"value":"18 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}