More Web Proxy on the site http://driver.im/

research-article

Faster energy maximization for faster maximum flow

Authors:

Aaron SidfordAuthors Info & Claims

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Pages 803 - 814

https://doi.org/10.1145/3357713.3384247

Published: 22 June 2020 Publication History

Abstract

In this paper we provide an algorithm which given any m-edge n-vertex directed graph with integer capacities at most U computes a maximum s-t flow for any vertices s and t in m ^11/8+o(1) U ^1/4 time with high probability. This running time improves upon the previous best of Õ(m ^10/7 U ^1/7) (Mądry 2016), Õ(m √n logU) (Lee Sidford 2014), and O(mn) (Orlin 2013) when the graph is not too dense or has large capacities.

We achieve this result by leveraging recent advances in solving undirected flow problems on graphs. We show that in the maximum flow framework of (Mądry 2016) the problem of optimizing the amount of perturbation of the central path needed to maximize energy and thereby reduce congestion can be efficiently reduced to a smoothed ℓ₂-ℓ_p flow optimization problem, which can be solved approximately via recent work (Kyng, Peng, Sachdeva, Wang 2019). Leveraging this new primitive, we provide a new interior point method for maximum flow with faster convergence and simpler analysis that no longer needs global potential functions involving energy as in previous methods (Mądry 2013, Mądry 2016).

References

[1]

Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. 2019. Iterative Refinement for ℓ _p-norm Regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019. 1405–1424. https://doi.org/10.1137/1.9781611975482.86

[2]

Zeyuan Allen Zhu, Zhenyu Liao, and Lorenzo Orecchia. 2015. Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. 237–245.

[3]

Paul Christiano, Jonathan A. Kelner, Aleksander Mądry, Daniel A. Spielman, and Shang-Hua Teng. 2011. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011. 273–282. https://doi.org/10.1145/1993636.1993674

Digital Library

[4]

Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. 2014. Solving SDD linear systems in nearly mlog^ 1/2n time. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 343–352. https://doi.org/10.1145/2591796.2591833

Digital Library

[5]

Michael B. Cohen, Yin Tat Lee, and Zhao Song. 2019. Solving linear programs in the current matrix multiplication time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. 938–942.

Digital Library

[6]

Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu. 2017. Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m^ 10/7 log W) Time (Extended Abstract). In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. 752–771.

Digital Library

[7]

Thomas H Cormen, Charles Eric Leiserson, Ronald L Rivest, and Clifford Stein. 2001. Introduction to algorithms. 6, MIT press Cambridge, MA.

[8]

Samuel I Daitch and Daniel A Spielman. 2008. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the fortieth annual ACM symposium on Theory of computing. 451–460.

Digital Library

[9]

Alina Ene, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. 2016. Routing under balance. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. 598–611. https://doi.org/10.1145/2897518.2897654

Digital Library

[10]

Shimon Even and R Endre Tarjan. 1975. Network flow and testing graph connectivity. SIAM journal on computing, 4, 4 (1975), 507–518.

[11]

Greg N Federickson. 1987. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16, 6 (1987), 1004–1022.

Digital Library

[12]

Lisa Fleischer. 2000. Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. SIAM J. Discrete Math., 13, 4 (2000), 505–520.

Digital Library

[13]

L. R. Ford and D. R. Fulkerson. 1956. Maximal Flow Through a Network. Canadian Journal of Mathematics, 8 (1956), 399–404. https://doi.org/10.4153/CJM-1956-045-5

[14]

Harold N Gabow and Robert E Tarjan. 1989. Faster scaling algorithms for network problems. SIAM J. Comput., 18, 5 (1989), 1013–1036.

Digital Library

[15]

Naveen Garg and Jochen Könemann. 1998. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. In 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA. 300–309.

[16]

Andrew V. Goldberg and Satish Rao. 1998. Beyond the Flow Decomposition Barrier. J. ACM, 45, 5 (1998), 783–797. https://doi.org/10.1145/290179.290181

Digital Library

[17]

John E Hopcroft and Richard M Karp. 1973. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2, 4 (1973), 225–231.

[18]

Motoki Ikeda and Shin-ichi Tanigawa. 2018. Cut Sparsifiers for Balanced Digraphs. In International Workshop on Approximation and Online Algorithms. 277–294.

[19]

Giuseppe F Italiano and Piotr Sankowski. 2010. Improved minimum cuts and maximum flows in undirected planar graphs. arXiv preprint arXiv:1011.2843.

[20]

Sanjiv Kapoor and Pravin M. Vaidya. 1996. Speeding up Karmarkar’s algorithm for multicommodity flows. Math. Program., 73 (1996), 111–127.

Digital Library

[21]

George Karakostas. 2008. Faster approximation schemes for fractional multicommodity flow problems. ACM Trans. Algorithms, 4, 1 (2008), 13:1–13:17.

Digital Library

[22]

Adam Karczmarz and Piotr Sankowski. 2019. Min-Cost Flow in Unit-Capacity Planar Graphs. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany. 66:1–66:17. https://doi.org/10.4230/LIPIcs.ESA.2019.66

[23]

David R Karger. 1997. Using random sampling to find maximum flows in uncapacitated undirected graphs. In Annual ACM Symposium on Theory of Computing: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. 4, 240–249.

Digital Library

[24]

David R Karger. 1998. Better random sampling algorithms for flows in undirected graphs. In SODA. 98, 490–499.

[25]

David R Karger. 1999. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24, 2 (1999), 383–413.

[26]

David R Karger and Matthew S Levine. 1998. Finding maximum flows in undirected graphs seems easier than bipartite matching. In STOC. 98, 69–78.

[27]

Alexander V Karzanov. 1973. O nakhozhdenii maksimal’nogo potoka v setyakh spetsial’nogo vida i nekotorykh prilozheniyakh. Mathematicheskie Voprosy Upravleniya Proizvodstvom.

[28]

Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2014. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014. 217–226. https://doi.org/10.1137/1.9781611973402.16

[29]

Jonathan A. Kelner, Gary L. Miller, and Richard Peng. 2012. Faster approximate multicommodity flow using quadratically coupled flows. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. 1–18. https://doi.org/10.1145/2213977.2213979

Digital Library

[30]

Jonathan A. Kelner and Aleksander Mądry. 2009. Faster Generation of Random Spanning Trees. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA. 13–21. https://doi.org/10.1109/FOCS.2009.75

[31]

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. 2013. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013. 911–920. https://doi.org/10.1145/2488608.2488724

Digital Library

[32]

Ioannis Koutis, Gary L. Miller, and Richard Peng. 2010. Approaching Optimality for Solving SDD Linear Systems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA. 235–244. https://doi.org/10.1109/FOCS.2010.29

Digital Library

[33]

Ioannis Koutis, Gary L. Miller, and Richard Peng. 2011. A Nearly-m log n Time Solver for SDD Linear Systems. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011. 590–598. https://doi.org/10.1109/FOCS.2011.85

Digital Library

[34]

Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. 2016. Sparsified Cholesky and multigrid solvers for connection laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. 842–850. https://doi.org/10.1145/2897518.2897640

Digital Library

[35]

Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Di Wang. 2019. Flows in almost linear time via adaptive preconditioning. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. 902–913. https://doi.org/10.1145/3313276.3316410

Digital Library

[36]

Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. 573–582. https://doi.org/10.1109/FOCS.2016.68

[37]

Yin Tat Lee, Satish Rao, and Nikhil Srivastava. 2013. A new approach to computing maximum flows using electrical flows. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013. 755–764. https://doi.org/10.1145/2488608.2488704

Digital Library

[38]

Yin Tat Lee and Aaron Sidford. 2014. Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014. 424–433. https://doi.org/10.1109/FOCS.2014.52

Digital Library

[39]

Yin Tat Lee and Aaron Sidford. 2015. Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. 230–249.

[40]

Yin Tat Lee and Aaron Sidford. 2019. Solving Linear Programs with Sqrt(rank) Linear System Solves. CoRR, abs/1910.08033 (2019), arxiv:1910.08033. arxiv:1910.08033

[41]

Yin Tat Lee and He Sun. 2015. Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. 250–269.

[42]

Yin Tat Lee and He Sun. 2017. An SDP-based algorithm for linear-sized spectral sparsification. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. 678–687.

Digital Library

[43]

Aleksander Madry. 2010. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010. 121–130.

Digital Library

[44]

Sanjay Mehrotra. 1992. On the implementation of a primal-dual interior point method. SIAM Journal on optimization, 2, 4 (1992), 575–601.

[45]

Karl Menger. 1927. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10, 1 (1927), 96–115.

[46]

Aleksander Mądry. 2013. Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA. 253–262. https://doi.org/10.1109/FOCS.2013.35

Digital Library

[47]

Aleksander Mądry. 2016. Computing Maximum Flow with Augmenting Electrical Flows. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA. 593–602. https://doi.org/10.1109/FOCS.2016.70

[48]

Aleksander Mądry, Damian Straszak, and Jakub Tarnawski. 2015. Fast Generation of Random Spanning Trees and the Effective Resistance Metric. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015. 2019–2036. https://doi.org/10.1137/1.9781611973730.134

[49]

Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi. 2012. Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. 1141–1160.

[50]

James B. Orlin. 2013. Max flows in O(nm) time, or better. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013. 765–774. https://doi.org/10.1145/2488608.2488705

Digital Library

[51]

Richard Peng. 2016. Approximate Undirected Maximum Flows in O(mpolylog(n)) Time. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. 1862–1867. https://doi.org/10.1137/1.9781611974331.ch130

[52]

John H Reif. 1983. Minimum s-t Cut of a Planar Undirected Network in O(n log^2(n)) Time. SIAM J. Comput., 12, 1 (1983), 71–81.

[53]

James Renegar. 1988. A polynomial-time algorithm, based on Newton’s method, for linear programming. Math. Program., 40, 1-3 (1988), 59–93.

[54]

Aaron Schild. 2018. An almost-linear time algorithm for uniform random spanning tree generation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018. 214–227. https://doi.org/10.1145/3188745.3188852

Digital Library

[55]

Jonah Sherman. 2013. Nearly Maximum Flows in Nearly Linear Time. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA. 263–269. https://doi.org/10.1109/FOCS.2013.36

Digital Library

[56]

Jonah Sherman. 2017. Area-convexity, l_ ∞ regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. 452–460. https://doi.org/10.1145/3055399.3055501

Digital Library

[57]

Aaron Sidford and Kevin Tian. 2018. Coordinate Methods for Accelerating ℓ _∞ Regression and Faster Approximate Maximum Flow. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018. 922–933. https://doi.org/10.1109/FOCS.2018.00091

[58]

Daniel A. Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008. 563–568.

[59]

Daniel A. Spielman and Shang-Hua Teng. 2003. Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m^ 1.31). CoRR, cs.DS/0310036 (2003), arxiv:cs.DS/0310036

[60]

Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. 81–90. https://doi.org/10.1145/1007352.1007372

Digital Library

[61]

Pravin M Vaidya. 1991. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A talk based on this manuscript, 2, 3.4 (1991), 2–4.

[62]

Christian Wulff-Nilsen. 2010. Min st-Cut of a Planar Graph in O (n loglog n) Time. arXiv preprint arXiv:1007.3609.

[63]

Yinyu Ye, Michael J Todd, and Shinji Mizuno. 1994. An O (√ nL)-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research, 19, 1 (1994), 53–67.

Cited By

Bernstein ABlikstad JSaranurak TTu T(2024)Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00123(2056-2077)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00123
Chen LKyng RLiu YPeng RGutenberg MSachdeva S(2023)Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost FlowCommunications of the ACM10.1145/361094066:12(85-92)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3610940
van den Brand JLiu YSidford ASaha BServedio R(2023)Dynamic Maxflow via Dynamic Interior Point MethodsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585135(1215-1228)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585135
Show More Cited By

Index Terms

Faster energy maximization for faster maximum flow
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

A faster algorithm for computing the girth of planar and bounded genus graphs

The girth of a graph G is the length of a shortest cycle of G. In this article we design an O(n^5/4 log n) algorithm for finding the girth of an undirected n-vertex planar graph, the first o(n²) algorithm for this problem. We also extend our results for ...
Detecting 2-joins faster

2-Joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole-free graphs, perfect graphs and claw-free graphs. Their detection is ...
Maximum Laplacian energy of unicyclic graphs

We study the Laplacian and the signless Laplacian energy of connected unicyclic graphs, obtaining a tight upper bound for this class of graphs. We also find the connected unicyclic graph on n vertices having largest (signless) Laplacian energy for 3n13. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 2020

1429 pages

ISBN:9781450369794

DOI:10.1145/3357713

General Chairs:
Konstantin Makarychev
Northwestern University, USA
,
Yury Makarychev
Toyota Technological Institute at Chicago, USA
,
Madhur Tulsiani
Toyota Technological Institute at Chicago, USA
,
Gautam Kamath
University of Waterloo, Canada
,
Program Chair:
Julia Chuzhoy
Toyota Technological Institute at Chicago, USA

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '20

Sponsor:

SIGACT

STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 22 - 26, 2020

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
273
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)3

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bernstein ABlikstad JSaranurak TTu T(2024)Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00123(2056-2077)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00123
Chen LKyng RLiu YPeng RGutenberg MSachdeva S(2023)Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost FlowCommunications of the ACM10.1145/361094066:12(85-92)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3610940
van den Brand JLiu YSidford ASaha BServedio R(2023)Dynamic Maxflow via Dynamic Interior Point MethodsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585135(1215-1228)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585135
Fountoulakis KLiu MGleich DMahoney M(2023)Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and PerformanceSIAM Review10.1137/20M133305565:1(59-143)Online publication date: 9-Feb-2023
https://doi.org/10.1137/20M1333055
Brand JChen LKyng RLiu YPeng RGutenberg MSachdeva SSidford A(2023)A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00037(503-514)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00037
van Den Brand JZhang D(2023)Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00036(493-502)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00036
de Vos T(2023)Minimum Cost Flow in the CONGEST ModelStructural Information and Communication Complexity10.1007/978-3-031-32733-9_18(406-426)Online publication date: 25-May-2023
https://doi.org/10.1007/978-3-031-32733-9_18
Malik VKarmakar S(2023)Some Insights on Dynamic Maintenance of Gomory-Hu Tree in Cactus Graphs and General GraphsAlgorithms and Discrete Applied Mathematics10.1007/978-3-031-25211-2_18(231-244)Online publication date: 26-Jan-2023
https://doi.org/10.1007/978-3-031-25211-2_18
Cruz‐Mejía OLetchford A(2023)A survey on exact algorithms for the maximum flow and minimum‐cost flow problemsNetworks10.1002/net.2216982:2(167-176)Online publication date: 20-Jun-2023
https://doi.org/10.1002/net.22169
Wang Y(2022)Max Flows in Planar Graphs with Vertex CapacitiesACM Transactions on Algorithms10.1145/350403218:1(1-27)Online publication date: 23-Jan-2022
https://dl.acm.org/doi/10.1145/3504032
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents