[1]   Sanjeev Arora, Elad Hazan, and Satyen Kale: The Multiplicative Weights Update method: A meta-algorithm and applications. Theory of Computing, 8(6):121–164, 2012. [doi:10.4086/toc.2012.v008a006]

[2]   Francisco Barahona: On the k-cut problem. Oper. Res. Lett., 26(3):99–105, 2000. [doi:10.1016/S0167-6377(99)00071-1]

[3]   Robert D. Carr, Lisa Fleischer, Vitus J. Leung, and Cynthia A. Phillips: Strengthening integrality gaps for capacitated network design and covering problems. In Proc. 11th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’00), pp. 106–115. SIAM, 2000. ACM DL.

[4]   Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, and Nitish Korula: Approximability of capacitated network design. Algorithmica, 72(2):493–514, 2015. Preliminary version in IPCO’11. [doi:10.1007/s00453-013-9862-4, arXiv:1009.5734]

[5]   Chandra Chekuri, Sudipto Guha, and Joseph Naor: The Steiner k-cut problem. SIAM J. Comput., 20(1):261–271, 2006. Preliminary version in ICALP’03. [doi:10.1137/S0895480104445095]

[6]   Chandra Chekuri and Kent Quanrud: Approximating the Held–Karp bound for metric TSP in nearly-linear time. In Proc. 58th FOCS, pp. 789–800. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.78, arXiv:1702.04307]

[7]   Chandra Chekuri and Kent Quanrud: Near-linear time approximation schemes for some implicit fractional packing problems. In Proc. 28th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’17), pp. 801–820. SIAM, 2017. [doi:10.1137/1.9781611974782.51]

[8]   Chandra Chekuri and Kent Quanrud: Fast approximations for metric-TSP via linear programming, 2018. [arXiv:1802.01242]

[9]   Chandra Chekuri and Kent Quanrud: Randomized MWU for positive LPs. In Proc. 29th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’18), pp. 358–377. SIAM, 2018. [doi:10.1137/1.9781611975031.25]

[10]   Chandra Chekuri and Kent Quanrud: On approximating (sparse) covering integer programs. In Proc. 30th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’19), pp. 1596–1615. SIAM, 2019. [doi:10.1137/1.9781611975482.97, arXiv:1807.11538]

[11]   Chandra Chekuri, Kent Quanrud, and Chao Xu: LP relaxation and tree packing for minimum k-cuts. SIAM J. Discr. Math., 34(2), 2020. Preliminary version in SOSA’19. [doi:10.1137/19M1299359, arXiv:1808.05765]

[12]   Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk: Designing FPT algorithms for cut problems using randomized contractions. SIAM J. Comput., 45(4):1171–1229, 2016. Preliminary version in FOCS’12. [doi:10.1137/15M1032077, arXiv:1207.4079]

[13]   Rodney G. Downey, Vladimir Estivill-Castro, Michael R. Fellows, Elena Prieto-Rodriguez, and Frances A. Rosamond: Cutting up is hard to do: The parameterized complexity of k-cut and elated problems. Electr. Notes Theoret. Comp. Sci., 78:209–222, 2003. [doi:10.1016/S1571-0661(04)81014-4]

[14]   Naveen Garg and Jochen Könemann: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 37(2):630–652, 2007. Preliminary version in FOCS’98. [doi:10.1137/S0097539704446232]

[15]   Michel X. Goemans and David P. Williamson: A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296–317, 1995. Preliminary version in SODA’92. [doi:10.1137/S0097539793242618]

[16]   Michel X. Goemans and David P. Williamson: The primal-dual method for approximation algorithms and its applications to network design problems. In Dorit S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, pp. 144–191. PWS Publishing Company, Boston, MA, 1996. ACM DL.

[17]   Andrew V. Goldberg and Satish Rao: Beyond the flow decomposition barrier. J. ACM, 45(5):783–797, 1998. Preliminary version in FOCS’97. [doi:10.1145/290179.290181]

[18]   Olivier Goldschmidt and Dorit S. Hochbaum: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res., 19(1):24–37, 1994. Preliminary version in FOCS’88. [doi:10.1287/moor.19.1.24]

[19]   Anupam Gupta, Euiwoong Lee, and Jason Li: Faster exact and approximate algorithms for k-cut. In Proc. 59th FOCS. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00020, arXiv:1807.08144]

[20]   Anupam Gupta, Euiwoong Lee, and Jason Li: An FPT algorithm beating 2-approximation for k-cut. In Proc. 29th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’18), pp. 2821–2837. SIAM, 2018. [doi:10.1137/1.9781611975031.179, arXiv:1710.08488]

[21]   Anupam Gupta, Euiwoong Lee, and Jason Li: The number of minimum k-cuts: improving the Karger–Stein bound. In Proc. 51st STOC, pp. 229–240. ACM Press, 2019. [doi:10.1145/3313276.3316395, arXiv:1906.00417]

[22]   Jianxiu Hao and James B. Orlin: A faster algorithm for finding the minimum cut in a directed graph. J. Algorithms, 17(3):424–446, 1994. Preliminary version in SODA’92. [doi:10.1006/jagm.1994.1043]

[23]   Dov Harel and Robert Endre Tarjan: Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338–355, 1984. [doi:10.1137/0213024]

[24]    Monika Henzinger, Satish Rao, and Di Wang: Local flow partitioning for faster edge connectivity. SIAM J. Comput., 49(1):1–36, 2020. Preliminary version in SODA’17. [doi:10.1137/18M1180335, arXiv:1704.01254]

[25]   Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723–760, 2001. Preliminary version in STOC’98. [doi:10.1145/502090.502095]

[26]   David R. Karger: Random Sampling in Graph Optimization Problems. Ph. D. thesis, Stanford University, 1994. Stanford CS TR-95-1541.

[27]   David R. Karger: Minimum cuts in near-linear time. J. ACM, 47(1):46–76, 2000. Preliminary version in STOC’96. [doi:10.1145/331605.331608, arXiv:cs/9812007]

[28]   David R. Karger and Clifford Stein: A new approach to the minimum cut problem. J. ACM, 43(4):601–640, 1996. Preliminary version in STOC’93. [doi:10.1145/234533.234534]

[29]   Ken-ichi Kawarabayashi and Mikkel Thorup: The minimum k-way cut of bounded size is fixed-parameter tractable. In Proc. 52nd FOCS, pp. 160–169. IEEE Comp. Soc., 2011. [doi:10.1109/FOCS.2011.53]

[30]   Ken-ichi Kawarabayashi and Mikkel Thorup: Deterministic global minimum cut of a simple graph in near-linear time. In Proc. 47th STOC, pp. 665–674. ACM Press, 2015. [doi:10.1145/2746539.2746588, arXiv:1411.5123]

[31]    Stavros G. Kolliopoulos and Neal E. Young: Approximation algorithms for covering/packing integer programs. J. Comput. System Sci., 71(4):495–505, 2005. Preliminary version in FOCS’01. [doi:10.1016/j.jcss.2005.05.002, arXiv:cs/0205030]

[32]   Yin Tat Lee and Aaron Sidford: Path finding methods for linear programming: Solving linear programs in Õ() iterations and faster algorithms for maximum flow. In Proc. 55th FOCS, pp. 424–433. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.52]

[33]   Matthew S. Levine: Fast randomized algorithms for computing minimum {3,4,5,6}-way cuts. In Proc. 11th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’00), pp. 735–742. SIAM, 2000. ACM DL.

[34]   On-Hei Solomon Lo, Jens M. Schmidt, and Mikkel Thorup: Compact cactus representation of all non-trivial min-cuts. Discr. Appl. Math., 303:296–304, 2021. [doi:10.1016/j.dam.2020.03.046, arXiv:1810.03865]

[35]   Aleksander Madry: Computing maximum flow with augmenting electrical flows. In Proc. 57th FOCS, pp. 593–602. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.70, arXiv:1608.06016]

[36]   Pasin Manurangsi: Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis. In Proc. 44th Internat. Colloq. on Automata, Languages, and Programming (ICALP’17), volume 80, pp. 79:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ICALP.2017.79]

[37]   David W. Matula: A linear time 2+ϵ approximation algorithm for edge connectivity. In Proc. 4th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’93), pp. 500–504. SIAM, 1993. ACM DL.

[38]    Hiroshi Nagamochi and Toshihide Ibaraki: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discr. Math., 5(1):54–66, 1992. Preliminary version in SIGAL’90. [doi:10.1137/0405004]

[39]   Hiroshi Nagamochi and Toshihide Ibaraki: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583–596, 1992. [doi:10.1007/BF01758778]

[40]   Hiroshi Nagamochi and Yoko Kamidoi: Minimum cost subpartitions in graphs. Inform. Process. Lett., 102(2–3):79–84, 2007. [doi:10.1016/j.ipl.2006.11.011]

[41]   Joseph Naor and Yuval Rabani: Tree packing and approximating k-cuts. In Proc. 12th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’01), pp. 26–27. SIAM, 2001. ACM DL.

[42]   Crispin St. J. A. Nash-Williams: Edge-disjoint spanning trees of finite graphs. J. London Math. Soc., 36(1):445–450, 1961. [doi:10.1112/jlms/s1-36.1.445]

[43]   Kent Quanrud: Fast and deterministic approximations for k-cut. In Proc. 22nd Internat. Conf. on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’19), pp. 23:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.23, arXiv:1807.07143]

[44]   Prasad Raghavendra and David Steurer: Graph expansion and the Unique Games Conjecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]

[45]   R. Ravi and Amitabh Sinha: Approximating k-cuts using network strengths as a Lagrangean relaxation. Eur. J. Operational Res., 186(1):77–90, 2008. Preliminary version in SODA’02. [doi:10.1016/j.ejor.2007.01.040]

[46]   Huzur Saran and Vijay V. Vazirani: Finding k cuts within twice the optimal. SIAM J. Comput., 24(1):101–108, 1995. Preliminary version in FOCS’91. [doi:10.1137/S0097539792251730]

[47]   Daniel Dominic Sleator and Robert Endre Tarjan: A data structure for dynamic trees. J. Comput. System Sci., 26(3):362–391, 1983. Preliminary version in STOC’81. [doi:10.1016/0022-0000(83)90006-5]

[48]   Mechthild Stoer and Frank Wagner: A simple min-cut algorithm. J. ACM, 44(4):585–591, 1997. Preliminary version in ESA’94. [doi:10.1145/263867.263872]

[49]   Mikkel Thorup: Minimum k-way cuts via deterministic greedy tree packing. In Proc. 40th STOC, pp. 159–166. ACM Press, 2008. [doi:10.1145/1374376.1374402]

[50]   William T. Tutte: On the problem of decomposing a graph into n connected components. J. London Math. Soc., 36(1):221–230, 1961. [doi:10.1112/jlms/s1-36.1.221]

[51]   Mingyu Xiao, Leizhen Cai, and Andrew Chi-Chih Yao: Tight approximation ratio of a general greedy splitting algorithm for the minimum k-way cut problem. Algorithmica, 59(4):510–520, 2011. [doi:10.1007/s00453-009-9316-1, arXiv:0811.3723]

[52]   Neal E. Young: Sequential and parallel algorithms for mixed packing and covering. In Proc. 42nd FOCS, pp. 538–546. IEEE Comp. Soc., 2001. [doi:10.1109/SFCS.2001.959930, arXiv:cs/0205039]

[53]    Neal E. Young: Nearly linear-work algorithms for mixed packing/covering and facility-location linear programs, 2014. [arXiv:1407.3015]