{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:06Z","timestamp":1773481986292,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1536002, CCF-1540541, CCF-1617790,"],"award-info":[{"award-number":["CCF-1536002, CCF-1540541, CCF-1617790,"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316395","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"229-240","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["The number of minimum\n            <i>k<\/i>\n            -cuts: improving the Karger-Stein bound"],"prefix":"10.1145","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[{"name":"New York University, USA"}]},{"given":"Jason","family":"Li","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.16"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Amir Abboud Virginia Vassilevska Williams and Oren Weimann. 2014. Consequences of faster alignment of sequences. In International Colloquium on Automata Languages and Programming. Springer 39\u201351.  Amir Abboud Virginia Vassilevska Williams and Oren Weimann. 2014. Consequences of faster alignment of sequences. In International Colloquium on Automata Languages and Programming. Springer 39\u201351.","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s A Bencz\u00far and Michel X. Goemans. 2008. Deformable polygon representation and near-mincuts. In Building Bridges. Springer 103\u2013135.  Andr\u00e1s A Bencz\u00far and Michel X. Goemans. 2008. Deformable polygon representation and near-mincuts. In Building Bridges. Springer 103\u2013135.","DOI":"10.1007\/978-3-540-85221-6_3"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00043-6"},{"key":"e_1_3_2_1_5_1","unstructured":"Karthekeyan Chandrasekaran Chao Xu and Xilin Yu. 2018.  Karthekeyan Chandrasekaran Chao Xu and Xilin Yu. 2018."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 1426\u20131438","author":"Hypergraph"},{"key":"e_1_3_2_1_7_1","unstructured":"Chandra Chekuri Sudipto Guha and Joseph Naor. 2006.  Chandra Chekuri Sudipto Guha and Joseph Naor. 2006."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"The Steiner k-cut problem. SIAM J. Discrete Math. 20 1 (2006) 261\u2013271. S0895480104445095  The Steiner k-cut problem. SIAM J. Discrete Math. 20 1 (2006) 261\u2013271. S0895480104445095","DOI":"10.1137\/S0895480104445095"},{"key":"e_1_3_2_1_9_1","unstructured":"Chandra Chekuri Kent Quanrud and Chao Xu. 2018. LP Relaxation and Tree Packing for Minimum k-cuts. arXiv preprint arXiv:1808.05765 (2018).  Chandra Chekuri Kent Quanrud and Chao Xu. 2018. LP Relaxation and Tree Packing for Minimum k-cuts. arXiv preprint arXiv:1808.05765 (2018)."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032077"},{"key":"e_1_3_2_1_11_1","unstructured":"Mohsen Ghaffari David R Karger and Debmalya Panigrahi. 2017.  Mohsen Ghaffari David R Karger and Debmalya Panigrahi. 2017."},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1101\u20131114","author":"Random"},{"key":"e_1_3_2_1_13_1","unstructured":"Olivier Goldschmidt and Dorit S. Hochbaum. 1994.  Olivier Goldschmidt and Dorit S. Hochbaum. 1994."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19 1 (1994) 24\u201337.   A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19 1 (1994) 24\u201337.","DOI":"10.1287\/moor.19.1.24"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00020"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175483"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1043"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00079-8"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/050631616"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_3_2_1_22_1","unstructured":"Ken-ichi Kawarabayashi and Bingkai Lin. 2018. A nearly 5 \/3-approximation FPT Algorithm for Min-k-Cut. Manuscript (2018).  Ken-ichi Kawarabayashi and Bingkai Lin. 2018. A nearly 5 \/3-approximation FPT Algorithm for Min-k-Cut. Manuscript (2018)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.53"},{"key":"e_1_3_2_1_24_1","unstructured":"Donald E Knuth. 1973.  Donald E Knuth. 1973."},{"key":"e_1_3_2_1_25_1","unstructured":"The Art of Computer Programming Volume 1: Fundamental Algorithms. Addison-Wesley Publishing Company.  The Art of Computer Programming Volume 1: Fundamental Algorithms. Addison-Wesley Publishing Company."},{"key":"e_1_3_2_1_26_1","unstructured":"Fran\u00e7ois Le Gall. 2014.  Fran\u00e7ois Le Gall. 2014."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/338219.338633"},{"key":"e_1_3_2_1_29_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"80","author":"Manurangsi Pasin","year":"2017"},{"key":"e_1_3_2_1_30_1","unstructured":"Ji\u0159\u00ed Matou\u0161ek. 1999.  Ji\u0159\u00ed Matou\u0161ek. 1999."},{"key":"e_1_3_2_1_31_1","unstructured":"Geometric discrepancy. Algorithms and Combinatorics Vol. 18. Springer-Verlag Berlin. xii+288 pages. 978- 3- 642- 03942- 3 An illustrated guide.  Geometric discrepancy. Algorithms and Combinatorics Vol. 18. Springer-Verlag Berlin. xii+288 pages. 978- 3- 642- 03942- 3 An illustrated guide."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405004"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Hiroshi Nagamochi and Toshihide Ibaraki. 2000. A fast algorithm for computing minimum 3-way and 4-way cuts. Math. Program. 88 3 Ser. A (2000) 507\u2013520.  Hiroshi Nagamochi and Toshihide Ibaraki. 2000. A fast algorithm for computing minimum 3-way and 4-way cuts. Math. Program. 88 3 Ser. A (2000) 507\u2013520.","DOI":"10.1007\/PL00011383"},{"key":"e_1_3_2_1_34_1","unstructured":"Hiroshi Nagamochi Shigeki Katayama and Toshihide Ibaraki. 2000.  Hiroshi Nagamochi Shigeki Katayama and Toshihide Ibaraki. 2000."},{"key":"e_1_3_2_1_35_1","unstructured":"A faster algorithm for computing minimum 5-way and 6-way cuts in graphs. J. Comb. Optim. 4 2 (2000) 151\u2013169.  A faster algorithm for computing minimum 5-way and 6-way cuts in graphs. J. Comb. Optim. 4 2 (2000) 151\u2013169."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365415"},{"key":"e_1_3_2_1_37_1","unstructured":"Kent Quanrud. 2018. Fast and Deterministic Approximations for k-Cut. arXiv preprint arXiv:1807.07143 (2018).  Kent Quanrud. 2018. Fast and Deterministic Approximations for k-Cut. arXiv preprint arXiv:1807.07143 (2018)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.01.040"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792251730"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374402"},{"key":"e_1_3_2_1_41_1","unstructured":"Virginia Vassilevska Williams. 2012.  Virginia Vassilevska Williams. 2012."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316395","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316395","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":43,"alternative-id":["10.1145\/3313276.3316395","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316395","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}