{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:56Z","timestamp":1740109316147,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T00:00:00Z","timestamp":1701820800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T00:00:00Z","timestamp":1701820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000646","name":"Japan Society for the Promotion of Science London","doi-asserted-by":"publisher","award":["JP19K22841","JP20H00609","JP20H05967"],"award-info":[{"award-number":["JP19K22841","JP20H00609","JP20H05967"]}],"id":[{"id":"10.13039\/501100000646","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s10107-023-02029-0","type":"journal-article","created":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T13:07:21Z","timestamp":1701868041000},"page":"717-732","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A polynomial time algorithm for finding a minimum 4-partition of a submodular function"],"prefix":"10.1007","volume":"207","author":[{"given":"Tsuyoshi","family":"Hirayama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuhao","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4417-3299","authenticated-orcid":false,"given":"Chao","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,6]]},"reference":[{"key":"2029_CR1","doi-asserted-by":"publisher","unstructured":"Beideman, C., Chandrasekaran, K., Wang, W.: Counting and enumerating optimum cut sets for hypergraph $$k$$-partitioning problems for fixed k. In: Boja\u0144czyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Leibniz International Proceedings in Informatics (LIPIcs), vol. 229, pp. 16:1\u201316:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2022.16. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2022\/16357","DOI":"10.4230\/LIPIcs.ICALP.2022.16"},{"key":"2029_CR2","doi-asserted-by":"publisher","unstructured":"Beideman, C., Chandrasekaran, K., Wang, W.: Deterministic enumeration of all minimum $$k$$-cut-sets in hypergraphs for fixed $$k$$. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2208\u20132228. Society for Industrial and Applied Mathematics, Philadelphia (2022). https:\/\/doi.org\/10.1137\/1.9781611977073","DOI":"10.1137\/1.9781611977073"},{"key":"2029_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01732-0","author":"C Beideman","year":"2021","unstructured":"Beideman, C., Chandrasekaran, K., Xu, C.: Multicriteria cuts and size-constrained $$k$$-cuts in hypergraphs. Math. Program. (2021). https:\/\/doi.org\/10.1007\/s10107-021-01732-0","journal-title":"Math. Program."},{"key":"2029_CR4","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\u201921, pp. 1026\u20131038. Society for Industrial and Applied Mathematics, USA (2021)","DOI":"10.1137\/1.9781611976465.64"},{"key":"2029_CR5","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1250","author":"K Chandrasekaran","year":"2022","unstructured":"Chandrasekaran, K., Chekuri, C.: Hypergraph $$k$$-cut for fixed $$k$$ in deterministic polynomial time. Math. Oper. Res. (2022). https:\/\/doi.org\/10.1287\/moor.2021.1250","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"2029_CR6","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(1\u20132), 85\u2013113 (2021). https:\/\/doi.org\/10.1007\/s10107-019-01443-7","journal-title":"Math. Program."},{"key":"2029_CR7","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Ene, A.: Approximation algorithms for submodular multiway partition. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 807\u2013816. IEEE, Palm Springs, CA, USA (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.34","DOI":"10.1109\/FOCS.2011.34"},{"issue":"2","key":"2029_CR8","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). https:\/\/doi.org\/10.1137\/19M1299359","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"2029_CR9","doi-asserted-by":"publisher","first-page":"2118","DOI":"10.1137\/18M1163865","volume":"47","author":"C Chekuri","year":"2018","unstructured":"Chekuri, C., Xu, C.: Minimum cuts and sparsification in hypergraphs. SIAM J. Comput. 47(6), 2118\u20132156 (2018). https:\/\/doi.org\/10.1137\/18M1163865","journal-title":"SIAM J. Comput."},{"key":"2029_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 Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 881\u2013896. SIAM (2019)","DOI":"10.1137\/1.9781611975482.54"},{"issue":"4","key":"2029_CR11","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). https:\/\/doi.org\/10.1016\/j.disopt.2013.10.002","journal-title":"Discrete Optim."},{"issue":"2\/3","key":"2029_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1023\/A:1009833626004","volume":"3","author":"L Gasieniec","year":"1999","unstructured":"Gasieniec, L., Jansson, J., Lingas, A., \u00d6stlin, A.: On the complexity of constructing evolutionary trees. J. Comb. Optim. 3(2\/3), 183\u2013197 (1999). https:\/\/doi.org\/10.1023\/A:1009833626004","journal-title":"J. Comb. Optim."},{"key":"2029_CR13","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.S.: A polynomial algorithm for the $$k$$-cut problem for fixed $$k$$. Math. Oper. Res. 19, 24\u201337 (1994). https:\/\/doi.org\/10.1287\/moor.19.1.24","journal-title":"Math. Oper. Res."},{"key":"2029_CR14","unstructured":"Guinez, F., Queyranne, M.: The size-constrained submodular $$k$$-partition problem (2012). https:\/\/docs.google.com\/viewer?a=v &pid=sites &srcid=ZGVmYXVsdGRvbWFpbnxmbGF2aW9ndWluZXpob21lcGFnZXxneDo0NDVlMThkMDg4ZWRlOGI1. Unpublished manuscript. See also https:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43309\/Queyranne.pdf"},{"key":"2029_CR15","doi-asserted-by":"publisher","DOI":"10.1145\/3478018","author":"A Gupta","year":"2021","unstructured":"Gupta, A., Harris, D.G., Lee, E., Li, J.: Optimal bounds for the $$k$$-cut problem. J. ACM (2021). https:\/\/doi.org\/10.1145\/3478018","journal-title":"J. ACM"},{"key":"2029_CR16","doi-asserted-by":"publisher","unstructured":"Gupta, A., Lee, E., Li, J.: Faster exact and approximate algorithms for k-cut. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 113\u2013123 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00020","DOI":"10.1109\/FOCS.2018.00020"},{"key":"2029_CR17","doi-asserted-by":"publisher","unstructured":"Hirayama, T., Liu, Y., Makino, K., Shi, K., Xu, C.: A polynomial time algorithm for finding a minimum 4-partition of a submodular function. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1680\u20131691. https:\/\/doi.org\/10.1137\/1.9781611977554.ch64","DOI":"10.1137\/1.9781611977554.ch64"},{"issue":"5","key":"2029_CR18","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1137\/050631616","volume":"36","author":"Y Kamidoi","year":"2006","unstructured":"Kamidoi, Y., Yoshida, N., Nagamochi, H.: A deterministic algorithm for finding all minimum $$k$$-way cuts. SIAM J. Comput. 36(5), 1329\u20131341 (2006). https:\/\/doi.org\/10.1137\/050631616","journal-title":"SIAM J. Comput."},{"key":"2029_CR19","unstructured":"Klimmek, R., Wagner, F.: A simple hypergraph min cut algorithm. Tech. Rep. B 96-02, FU Berlin Fachbereich Mathematik und Informatik (1996)"},{"key":"2029_CR20","doi-asserted-by":"publisher","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.W.: A faster cutting plane method and its implications for combinatorial and convex optimization. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049\u20131065 (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.68","DOI":"10.1109\/FOCS.2015.68"},{"issue":"1","key":"2029_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-9260(00)00008-0","volume":"30","author":"WK Mak","year":"2000","unstructured":"Mak, W.K., Wong, D.F.: Fast hypergraph min-cut algorithm for circuit partitioning. Integr. VLSI J. 30(1), 1\u201311 (2000). https:\/\/doi.org\/10.1016\/S0167-9260(00)00008-0","journal-title":"Integr. VLSI J."},{"issue":"10","key":"2029_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1002\/ecjc.20341","volume":"90","author":"H Nagamochi","year":"2007","unstructured":"Nagamochi, H.: Algorithms for the minimum partitioning problems in graphs. Electron. Commun. Jpn. 90(10), 63\u201378 (2007). https:\/\/doi.org\/10.1002\/ecjc.20341. (Part III Fundamental Electronic Science)","journal-title":"Electron. Commun. Jpn."},{"issue":"1","key":"2029_CR23","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math. 5(1), 54\u201366 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"2029_CR24","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/PL00011383","volume":"88","author":"H Nagamochi","year":"2000","unstructured":"Nagamochi, H., Ibaraki, T.: A fast algorithm for computing minimum 3-way and 4-way cuts. Math. Program. 88(3), 507\u2013520 (2000). https:\/\/doi.org\/10.1007\/PL00011383","journal-title":"Math. Program."},{"issue":"2","key":"2029_CR25","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1023\/A:1009804919645","volume":"4","author":"H Nagamochi","year":"2000","unstructured":"Nagamochi, H., Katayama, S., Ibaraki, T.: A faster algorithm for computing minimum 5-way and 6-way cuts in graphs. J. Comb. Optim. 4(2), 151\u2013169 (2000). https:\/\/doi.org\/10.1023\/A:1009804919645","journal-title":"J. Comb. Optim."},{"key":"2029_CR26","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-10631-6_8","volume-title":"Algorithms and Computation","author":"K Okumoto","year":"2009","unstructured":"Okumoto, K., Fukunaga, T., Nagamochi, H.: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. In: Dong, Y., Du, D.Z., Ibarra, O. (eds.) Algorithms and Computation, pp. 55\u201364. Springer, Berlin (2009)"},{"key":"2029_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9483-0","author":"K Okumoto","year":"2010","unstructured":"Okumoto, K., Fukunaga, T., Nagamochi, H.: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica (2010). https:\/\/doi.org\/10.1007\/s00453-010-9483-0","journal-title":"Algorithmica"},{"issue":"1","key":"2029_CR28","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01585863","volume":"82","author":"M Queyranne","year":"1998","unstructured":"Queyranne, M.: Minimizing symmetric submodular functions. Math. Program. 82(1), 3\u201312 (1998). https:\/\/doi.org\/10.1007\/BF01585863","journal-title":"Math. Program."},{"key":"2029_CR29","doi-asserted-by":"publisher","unstructured":"Thorup, M.: Minimum $$k$$-way cuts via deterministic greedy tree packing. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 159\u2013165 (2008). https:\/\/doi.org\/10.1145\/1374376.1374402","DOI":"10.1145\/1374376.1374402"},{"key":"2029_CR30","doi-asserted-by":"crossref","unstructured":"Vazirani, V.V., Yannakakis, M.: Suboptimal cuts: Their enumeration, weight and number. In: International Colloquium on Automata, Languages, and Programming, pp. 366\u2013377. Springer (1992)","DOI":"10.1007\/3-540-55719-9_88"},{"key":"2029_CR31","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-92182-0_21","volume-title":"Algorithms and Computation","author":"M Xiao","year":"2008","unstructured":"Xiao, M.: An improved divide-and-conquer algorithm for finding all minimum k-way cuts. In: Hong, S.H., Nagamochi, H., Fukunaga, T. (eds.) Algorithms and Computation, pp. 208\u2013219. Springer, Berlin (2008)"},{"issue":"14\u201315","key":"2029_CR32","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. 110(14\u201315), 554\u2013558 (2010). https:\/\/doi.org\/10.1016\/j.ipl.2010.05.003","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"2029_CR33","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00453-009-9284-5","volume":"56","author":"LP Yeh","year":"2010","unstructured":"Yeh, L.P., Wang, B.F., Su, H.H.: Efficient algorithms for the problems of enumerating cuts by non-decreasing weights. Algorithmica 56(3), 297\u2013312 (2010). https:\/\/doi.org\/10.1007\/s00453-009-9284-5","journal-title":"Algorithmica"},{"issue":"1","key":"2029_CR34","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.dam.2003.10.007","volume":"143","author":"L Zhao","year":"2004","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: On generalized greedy splitting algorithms for multiway partition problems. Discrete Appl. Math. 143(1), 130\u2013143 (2004). https:\/\/doi.org\/10.1016\/j.dam.2003.10.007","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"2029_CR35","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). https:\/\/doi.org\/10.1007\/s10107-004-0510-2","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02029-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02029-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02029-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T15:09:36Z","timestamp":1723043376000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02029-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,6]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["2029"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02029-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,12,6]]},"assertion":[{"value":"21 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}