{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T15:07:01Z","timestamp":1768748821174,"version":"3.49.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T00:00:00Z","timestamp":1682553600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T00:00:00Z","timestamp":1682553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00493-023-00021-y","type":"journal-article","created":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T10:02:06Z","timestamp":1682589726000},"page":"455-477","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Min\u2013Max Partitioning of Hypergraphs and Symmetric Submodular Functions"],"prefix":"10.1007","volume":"43","author":[{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"first","affiliation":[]},{"given":"Chandra","family":"Chekuri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,27]]},"reference":[{"issue":"2","key":"21_CR1","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":"21_CR2","doi-asserted-by":"crossref","unstructured":"Beideman, C., Chandrasekaran, K., Wang, W.: Counting and enumerating optimum cut sets for hypergraph $$k$$-partitioning problems for fixed $$k$$. In: International Colloquium on Automata, Languages and Programming, ICALP, pp.\u00a016:1\u201316:18 (2022)","DOI":"10.1287\/moor.2022.0259"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.dam.2014.07.028","volume":"180","author":"A Bern\u00e1th","year":"2015","unstructured":"Bern\u00e1th, A., Kir\u00e1ly, Z.: On the tractability of some natural packing, covering and partitioning problems. Discret. Appl. Math. 180, 25\u201335 (2015)","journal-title":"Discret. Appl. Math."},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Chekuri, C.: Hypergraph $$k$$-cut for fixed $$k$$ in deterministic polynomial time, Mathematics of Operations Research (2022), Prelim. version in FOCS (2020)","DOI":"10.1109\/FOCS46700.2020.00080"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s10107-019-01443-7","volume":"186","author":"K Chandrasekaran","year":"2021","unstructured":"Chandrasekaran, K., Xu, C., Yu, X.: Hypergraph $$k$$-Cut in randomized polynomial time. Math. Program. 186, 85\u2013113 (2021)","journal-title":"Math. Program."},{"key":"21_CR6","unstructured":"Chandrasekaran, K., Zhang, X.: Private communication"},{"key":"21_CR7","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, pp.\u00a0807\u2013816 (2011)","DOI":"10.1109\/FOCS.2011.34"},{"issue":"14","key":"21_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2020.v016a014","volume":"16","author":"C Chekuri","year":"2020","unstructured":"Chekuri, C., Li, S.: On the hardness of approximating the $$k$$-way hypergraph cut problem. Theory Comput. 16(14), 1\u20138 (2020)","journal-title":"Theory Comput."},{"issue":"2","key":"21_CR9","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. Discret. Math. 34(2), 1334\u20131353 (2020)","journal-title":"SIAM J. Discret. Math."},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Fox, K., Panigrahi, D., Zhang, F.: Minimum cut and minimum $$k$$-cut in hypergraphs via branching contractions. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.\u00a0881\u2013896 (2019)","DOI":"10.1137\/1.9781611975482.54"},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BF01192523","volume":"15","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Ramakrishnan, V.S.: Minimizing submodular functions over families of sets. Combinatorica 15, 499\u2013513 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"21_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":"21_CR13","unstructured":"Guinez, F., Queyranne, M.: The size-constrained submodular k-partition problem, Unpublished manuscript. https:\/\/docs.google.com\/viewer?a=v &pid=sites &srcid=ZGVmYXVsdGRvbWFpbnxmbGF2aW9ndWluZXpob21lcGFnZXxneDo0NDVlMThkMDg4ZWRlOGI1. See also https:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43309\/Queyranne.pdf (2012)"},{"key":"21_CR14","unstructured":"Gupta, A., Harris, D., Lee, E., Li, J.: Optimal bounds for the $$k$$-cut problem. Preprint in arXiv arxiv:2005.08301 (2020)"},{"key":"21_CR15","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, pp.\u00a0473\u2013484 (2020)","DOI":"10.1145\/3357713.3384285"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Hirayama, T., Liu, K., Makino, Y., Shi, K., Xu, C.: A polynomial time algorithm for finding a minimum $$4$$-partition of a submodular function, (To appear) Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2023)","DOI":"10.1137\/1.9781611977554.ch64"},{"issue":"5","key":"21_CR17","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":"1","key":"21_CR18","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"D Karger","year":"2000","unstructured":"Karger, D.: Minimum cuts in near-linear time. J. ACM 47(1), 46\u201376 (2000)","journal-title":"J. ACM"},{"issue":"4","key":"21_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":"21_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":"21_CR21","doi-asserted-by":"publisher","first-page":"1","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), 1\u201322 (2018)","journal-title":"Algorithms"},{"key":"21_CR22","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1007\/s00493-019-3900-1","volume":"39","author":"M N\u00e4gele","year":"2019","unstructured":"N\u00e4gele, M., Sudakov, B., Zenklusen, R.: Submodular minimization under congruency constraints. Combinatorica 39, 1351\u20131386 (2019)","journal-title":"Combinatorica"},{"issue":"3","key":"21_CR23","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":"21_CR24","unstructured":"Queyranne, M.: On optimum size-constrained set partitions, Talk at Aussois workshop on Combinatorial Optimization (1999)"},{"issue":"1","key":"21_CR25","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":"21_CR26","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics. Springer, New York (2003)"},{"issue":"6","key":"21_CR27","doi-asserted-by":"publisher","first-page":"1715","DOI":"10.1137\/100783352","volume":"40","author":"Z Svitkina","year":"2011","unstructured":"Svitkina, Z., Fleischer, L.: Submodular approximation: sampling-based algorithms and lower bounds. SIAM J. Comput. 40(6), 1715\u20131737 (2011)","journal-title":"SIAM J. Comput."},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"Svitkina, Z., Tardos, \u00c9.: Min-max multiway cut. In: Approximation, Randomization, and Combinatorial Optimization. APPROX, Algorithms and Techniques, pp. 207\u2013218 (2004)","DOI":"10.1007\/978-3-540-27821-4_19"},{"key":"21_CR29","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.\u00a0159\u2013166 (2008)","DOI":"10.1145\/1374376.1374402"},{"key":"21_CR30","first-page":"2233","volume":"28","author":"K Wei","year":"2015","unstructured":"Wei, K., Iyer, R., Wang, S., Bai, W., Bilmes, J.: Mixed robust\/average submodular partitioning: fast algorithms, guarantees, and applications. Adv. Neural Inf. Process. Syst. 28, 2233\u20132241 (2015)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"21_CR31","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, pp.\u00a0208\u2013219 (2008)","DOI":"10.1007\/978-3-540-92182-0_21"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00021-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00021-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00021-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T09:04:32Z","timestamp":1729328672000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00021-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,27]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["21"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00021-y","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,27]]},"assertion":[{"value":"8 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}