pith. sign in

arxiv: 1906.10340 · v1 · pith:BDKYK6XSnew · submitted 2019-06-25 · 💻 cs.DS

Flows in Almost Linear Time via Adaptive Preconditioning

Rasmus Kyng , Richard Peng , Sushant Sachdeva , Di Wang This is my paper

Pith reviewed 2026-05-25 16:36 UTC · model grok-4.3

classification 💻 cs.DS
keywords flow algorithmsalmost-linear timepreconditioningexpander decompositionlp norm flowsmax flow approximationtotal variation minimizationgraph regression
0
0 comments X

The pith

Algorithms solve ℓp-norm flow problems on unit-weighted graphs to high accuracy in almost-linear time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces methods that handle a broad set of flow and regression tasks on graphs where all edges have weight one, reaching accuracy within one plus one over a polynomial in the number of vertices, all in time nearly proportional to the graph size. These tasks cover minimizing the ℓp norm of flows for p values that grow slowly with n but stay below a polylogarithmic threshold, along with the corresponding dual regression problems. The work shows that as p grows large the solutions approach max-flow and min-cut, and it extends the same techniques to approximate total variation minimization on discrete graphs. A sympathetic reader would care because prior methods for these problems incurred higher logarithmic factors or required stronger assumptions on edge weights, so removing those barriers opens faster computation for network design and image processing tasks that reduce to such flows.

Core claim

We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to (1 + 1 / poly(n)) accuracy in almost-linear time. These problems include ℓp-norm minimizing flow for p large (p ∈ [ω(1), o(log^{2/3} n)]), and their duals, ℓp-norm semi-supervised learning for p close to 1. As p tends to infinity, ℓp-norm flow and its dual tend to max-flow and min-cut respectively. Using this connection and our algorithms, we give an alternate approach for approximating undirected max-flow, and the first almost-linear time approximations of discretizations of total variation minimization objectives. The algorithm is based on the routing-based solver for Laplacian linear

What carries the argument

Adaptive non-linear preconditioning together with tree-routing ultra-sparsification for mixed ℓ2 and ℓp objectives and decomposition of the graph into uniform expanders.

If this is right

  • Approximating undirected max-flow becomes possible through the large-p limit of the flow problems.
  • Discretizations of total variation minimization objectives now admit almost-linear time approximations for the first time.
  • The same framework yields almost-linear time solutions for ℓp-norm semi-supervised learning when p is close to 1.
  • Tools previously restricted to linear systems now apply directly to a wider family of convex objectives without additional logarithmic overhead.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same preconditioning ideas could plausibly extend to other convex objectives that mix quadratic and higher-norm terms on graphs.
  • Relaxing the unit-weight restriction while preserving the runtime would immediately enlarge the set of practical instances.
  • Connections between the expander decomposition step and the choice of p range suggest that tighter expander constructions might push the allowable p interval higher.

Load-bearing premise

The new adaptive non-linear preconditioning and tree-routing ultra-sparsification can be combined without extra logarithmic factors, and the unit-weight assumption together with the stated range of p suffice for the expander decomposition to deliver the claimed runtime.

What would settle it

An explicit unit-weighted graph and p value inside the stated range on which the algorithm either exceeds almost-linear runtime or returns a flow whose objective value deviates from the optimum by more than 1/poly(n).

read the original abstract

We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to $(1 + 1 / poly(n))$ accuracy in almost-linear time. These problems include $\ell_p$-norm minimizing flow for $p$ large ($p \in [\omega(1), o(\log^{2/3} n) ]$), and their duals, $\ell_p$-norm semi-supervised learning for $p$ close to $1$. As $p$ tends to infinity, $\ell_p$-norm flow and its dual tend to max-flow and min-cut respectively. Using this connection and our algorithms, we give an alternate approach for approximating undirected max-flow, and the first almost-linear time approximations of discretizations of total variation minimization objectives. This algorithm demonstrates that many tools previous viewed as limited to linear systems are in fact applicable to a much wider range of convex objectives. It is based on the the routing-based solver for Laplacian linear systems by Spielman and Teng (STOC '04, SIMAX '14), but require several new tools: adaptive non-linear preconditioning, tree-routing based ultra-sparsification for mixed $\ell_2$ and $\ell_p$ norm objectives, and decomposing graphs into uniform expanders.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper claims algorithms for solving a class of flow and regression problems (including ℓ_p-norm minimizing flows for p ∈ [ω(1), o(log^{2/3} n)] and duals) on unit-weighted graphs to (1 + 1/poly(n)) accuracy in almost-linear time. The approach extends the Spielman-Teng routing-based Laplacian solver via three new primitives: adaptive non-linear preconditioning, tree-routing ultra-sparsification for mixed ℓ2/ℓp objectives, and decomposition into uniform expanders. As p → ∞ the problems approach max-flow/min-cut, yielding an alternate almost-linear-time approach to undirected max-flow approximation and the first such approximations for discretizations of total variation minimization.

Significance. If the runtime and accuracy claims hold, the result meaningfully extends almost-linear-time methods from linear systems to a broader family of convex objectives while preserving the unit-weight and stated p-range assumptions. It supplies an explicit composition of the new primitives that avoids extra logarithmic factors and demonstrates that routing-based techniques apply beyond ℓ2. The manuscript ships no machine-checked proofs or code, but the parameter-free character of the final runtime (once the primitives are established) is a strength.

major comments (3)
  1. [§3] §3 (Adaptive Non-linear Preconditioning): the analysis must explicitly bound the number of adaptive iterations and the per-iteration cost of the mixed-norm tree-routing step so that the overall dependence on p remains o(log^{2/3} n) rather than introducing an extra log factor; the current sketch does not display the recurrence that rules this out.
  2. [§4] §4 (Tree-Routing Ultra-Sparsification): the ultra-sparsifier construction for mixed ℓ2/ℓp objectives is stated to preserve the expander decomposition property, but the proof must verify that the distortion introduced by the ℓp component does not degrade the expansion parameter below the threshold required for the subsequent Spielman-Teng invocation; a concrete distortion bound (e.g., via the definition of the mixed-norm potential) is needed.
  3. [§5] §5 (Expander Decomposition): the unit-weight assumption is used to obtain uniform expanders whose conductance yields the claimed almost-linear runtime; the argument should quantify how the o(log^{2/3} n) upper bound on p interacts with the decomposition depth to avoid an extra poly(log n) factor when p is at the upper end of the interval.
minor comments (2)
  1. [Introduction] The abstract states the p-interval but the introduction should include a short table or paragraph contrasting the new range with prior almost-linear results (e.g., p = O(1) or p = Ω(log n)) to clarify the advance.
  2. Notation for the mixed-norm objective (Eq. (2) or wherever first defined) should explicitly separate the ℓ2 and ℓp terms so that the preconditioner update rule is unambiguous.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive feedback. The three major comments identify places where the analysis sketches in §§3–5 require additional explicit bounds and recurrences to confirm the claimed runtime. We agree these details strengthen the manuscript and will incorporate them in the revision. Below we respond point-by-point.

read point-by-point responses

  1. Referee: [§3] §3 (Adaptive Non-linear Preconditioning): the analysis must explicitly bound the number of adaptive iterations and the per-iteration cost of the mixed-norm tree-routing step so that the overall dependence on p remains o(log^{2/3} n) rather than introducing an extra log factor; the current sketch does not display the recurrence that rules this out.

    Authors: We agree the current sketch in §3 is insufficient. In the revised manuscript we will add a new lemma (Lemma 3.X) that derives the recurrence for the number of adaptive iterations. The recurrence solves to O(log log n) iterations when p = o(log^{2/3} n), with each iteration invoking the mixed-norm tree-routing primitive at cost Õ(m) after the ultra-sparsifier is built. The product of these quantities remains o(log^{2/3} n) overall, preserving the target runtime. We will also include the explicit potential-function argument that controls the per-iteration cost. revision: yes

  2. Referee: [§4] §4 (Tree-Routing Ultra-Sparsification): the ultra-sparsifier construction for mixed ℓ2/ℓp objectives is stated to preserve the expander decomposition property, but the proof must verify that the distortion introduced by the ℓp component does not degrade the expansion parameter below the threshold required for the subsequent Spielman-Teng invocation; a concrete distortion bound (e.g., via the definition of the mixed-norm potential) is needed.

    Authors: We accept this observation. The revised §4 will contain a new claim (Claim 4.Y) that bounds the multiplicative distortion of the mixed-norm potential by 1 + o(1) when p = o(log^{2/3} n). The proof proceeds by relating the mixed-norm stretch to the ℓ2 stretch of the underlying tree plus an additive term controlled by the p-norm of the residual; this term is shown to be negligible relative to the conductance threshold required by the Spielman-Teng solver. The resulting expansion parameter remains Ω(1/poly(log n)), which is sufficient for the subsequent invocation. revision: yes

  3. Referee: [§5] §5 (Expander Decomposition): the unit-weight assumption is used to obtain uniform expanders whose conductance yields the claimed almost-linear runtime; the argument should quantify how the o(log^{2/3} n) upper bound on p interacts with the decomposition depth to avoid an extra poly(log n) factor when p is at the upper end of the interval.

    Authors: We will strengthen the argument in §5. The revised text will include an explicit calculation (Lemma 5.Z) showing that the decomposition depth is O(log n / log log n) and that the p-dependent term in the conductance bound contributes only an additional o(log^{2/3} n) factor when multiplied by the depth. Because the unit-weight assumption already guarantees uniform expansion independent of p inside the stated range, the product stays inside the almost-linear regime. The calculation will be placed immediately after the statement of the expander decomposition theorem. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's derivation composes new primitives (adaptive non-linear preconditioning and tree-routing ultra-sparsification for mixed ℓ2/ℓp objectives) with the external Spielman-Teng routing solver for Laplacians. No load-bearing step reduces by construction to a fitted input, self-definition, or self-citation chain; the unit-weight assumption and p-range are stated explicitly as enabling the expander decomposition without internal tautology. The central runtime claim therefore retains independent algorithmic content.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard graph-theoretic assumptions (unit edge weights, undirected graphs) and on the correctness of three new algorithmic primitives whose details are not supplied in the abstract; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Undirected unit-weighted graphs admit the stated expander decomposition and tree-routing sparsification with the claimed parameters.
    Invoked implicitly when the abstract claims almost-linear time for the given p-range.

pith-pipeline@v0.9.0 · 5756 in / 1274 out tokens · 26341 ms · 2026-05-25T16:36:16.794409+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

64 extracted references · 64 canonical work pages · 21 internal anchors

  1. [1]

    Iterative refinement for _p -norm regression

    Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. Iterative refinement for _p -norm regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 , 2019

    work page 2019

  2. [2]

    Phase transition in the family of p-resistances

    Morteza Alamgir and Ulrike V Luxburg. Phase transition in the family of p-resistances. In Advances in Neural Information Processing Systems , pages 379--387, 2011

    work page 2011

  3. [3]

    Much Faster Algorithms for Matrix Scaling

    Zeyuan Allen - Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In Symposium on Foundations of Computer Science (FOCS) , pages 890--901, 2017. Available at: https://arxiv.org/abs/1704.02315

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  4. [4]

    Using petal-decompositions to build a low stretch spanning tree

    Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning tree. In STOC , 2012

    work page 2012

  5. [5]

    Cohen, Yin Tat Lee, and Yuanzhi Li

    S \'e bastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li. An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2018, pages 1130--1137, New York, NY, USA, 2018. ACM

    work page 2018

  6. [6]

    Bencz\' u r and David R

    Andr\' a s A. Bencz\' u r and David R. Karger. Approximating s-t minimum cuts in O (n^2) time. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , STOC '96, pages 47--55, New York, NY, USA, 1996. ACM

    work page 1996

  7. [7]

    Near-optimal approximate shortest paths and transshipment in distributed and streaming models

    Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria , pages 7:1--7:16, 2017. Available at: https://arxiv.org/abs/1607.05127

    work page arXiv 2017

  8. [8]

    Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs

    Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the 43rd annual ACM symposium on Theory of computing , STOC '11, pages 273--282, New York, NY, USA, 2011. ACM. Available at http://arxiv.org/abs...

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  9. [9]

    Cohen, Rasmus Kyng, Gary L

    Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup Rao, and Shen Chen Xu. Solving SDD linear systems in nearly m ^ 1/2 n time. In STOC , pages 343--352, 2014

    work page 2014

  10. [10]

    Runtime Guarantees for Regression Problems

    Hui Han Chin, Aleksander M a dry, Gary L. Miller, and Richard Peng. Runtime guarantees for regression problems. In Proceedings of the 4 th conference on Innovations in Theoretical Computer Science , ITCS '13, pages 269--282, New York, NY, USA, 2013. ACM. Available at http://arxiv.org/abs/1110.1358

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  11. [11]

    Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods

    Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton's method and interior point methods. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 902--913, 2017. Available at: https://arxiv.org/abs/1704.02310

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  12. [12]

    $\ell_p$ Row Sampling by Lewis Weights

    Michael B. Cohen and Richard Peng. _p row sampling by L ewis weights. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing , STOC '15, pages 183--192, New York, NY, USA, 2015. ACM. Available at http://arxiv.org/abs/1412.0588

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  13. [13]

    Faster Approximate Lossy Generalized Flow via Interior Point Algorithms

    Samuel I. Daitch and Daniel A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th annual ACM symposium on Theory of computing , STOC '08, pages 451--460, New York, NY, USA, 2008. ACM. Available at http://arxiv.org/abs/0803.0988

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  14. [14]

    Asymptotic behavior of _p -based L aplacian regularization in semi-supervised learning

    Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J Wainwright, and Michael I Jordan. Asymptotic behavior of _p -based L aplacian regularization in semi-supervised learning. In Conference on Learning Theory , pages 879--906, 2016

    work page 2016

  15. [15]

    Paths, trees, and flowers

    Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics , 17(3):449--467, 1965. Available at: https://cms.math.ca/10.4153/CJM-1965-045-4

    work page doi:10.4153/cjm-1965-045-4 1965

  16. [16]

    Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM , 19(2):248--264, 1972

    work page 1972

  17. [17]

    Network flow and testing graph connectivity

    Shimon Even and Robert Endre Tarjan. Network flow and testing graph connectivity. SIAM J. Comput. , 4(4):507--518, 1975

    work page 1975

  18. [18]

    Near-Optimal Distributed Maximum Flow

    Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt - Shamir. Near-optimal distributed maximum flow: Extended abstract. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti \' a n, Spain, July 21 - 23, 2015 , pages 81--90, 2015. Available at: https://arxiv.org/abs/1...

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  19. [19]

    Network flow and generalized path compression

    Zvi Galil and Amnon Naamad. Network flow and generalized path compression. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA , pages 13--26, 1979

    work page 1979

  20. [20]

    Goldberg and Satish Rao

    Andrew V. Goldberg and Satish Rao. Beyond the flow decomposition barrier. J. ACM , 45(5):783--797, 1998

    work page 1998

  21. [21]

    Goldberg and Robert Endre Tarjan

    Andrew V. Goldberg and Robert Endre Tarjan. A new approach to the maximum-flow problem. J. ACM , 35(4):921--940, 1988

    work page 1988

  22. [22]

    Goldberg and Robert Endre Tarjan

    Andrew V. Goldberg and Robert Endre Tarjan. Efficient maximum flow algorithms. Commun. ACM , 57(8):82--89, 2014

    work page 2014

  23. [23]

    Hopcroft and Richard M

    John E. Hopcroft and Richard M. Karp. An n^ 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. , 2(4):225--231, 1973

    work page 1973

  24. [24]

    Hochbaum and James B

    Dorit S. Hochbaum and James B. Orlin. Simplifications and speedups of the pseudoflow algorithm. Networks , 61(1):40--57, 2013

    work page 2013

  25. [25]

    The pseudoflow algorithm: A new algorithm for the maximum-flow problem

    Dorit S Hochbaum. The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations research , 56(4):992--1009, 2008

    work page 2008

  26. [26]

    Karzanov

    Alexander V. Karzanov. O nakhozhdenii maksimal\' nogo potoka v setyakh spetsial\'nogo vida i nekotorykh prilozheniyakh. Matematicheskie Voprosy Upravleniya Proizvodstvom , 5:81--94, 1973. In Russian, title translation: on finding maximum flows in networks with special structure and some applications

    work page 1973

  27. [27]

    Applications of parametric maxflow in computer vision

    Vladimir Kolmogorov, Yuri Boykov, and Carsten Rother. Applications of parametric maxflow in computer vision. In Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on , pages 1--8. IEEE, 2007

    work page 2007

  28. [28]

    An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

    Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 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 , pages 217--226, 2014. Availab...

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  29. [29]

    Kelner and A

    J.A. Kelner and A. Madry. Faster generation of random spanning trees . In FOCS , 2009

    work page 2009

  30. [30]

    Electric routing and concurrent flow cutting

    Jonathan A. Kelner and Petar Maymounkov. Electric routing and concurrent flow cutting. Theor. Comput. Sci. , 412(32):4123--4135, 2011. Available at: https://arxiv.org/abs/0909.2859

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  31. [31]

    A nearly-mlogn time solver for SDD linear systems

    Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for SDD linear systems. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , FOCS '11, pages 590--598, Washington, DC, USA, 2011. IEEE Computer Society. Available at http://arxiv.org/abs/1102.4842

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  32. [32]

    Miller, and Richard Peng

    Ioannis Koutis, Gary L. Miller, and Richard Peng. A fast solver for a class of linear systems. Communications of the ACM , 55(10):99--107, October 2012. Available at https://cacm.acm.org/magazines/2012/10/155538-a-fast-solver-for-a-class-of-linear-systems/fulltext

    work page 2012

  33. [33]

    Approaching optimality for solving SDD systems

    I. Koutis, G. Miller, and R. Peng. Approaching optimality for solving sdd linear systems. SIAM Journal on Computing , 43(1):337--354, 2014. Available at http://arxiv.org/abs/1003.2958

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  34. [34]

    J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu. A simple, combinatorial algorithm for solving sdd systems in nearly-linear time. In STOC , 2013

    work page 2013

  35. [35]

    R. Kyng, A. B. Rao, S. Sachdeva, and D. A Spielman. Algorithms for lipschitz learning on graphs. In COLT , 2015

    work page 2015

  36. [36]

    Karger and Clifford Stein

    David R. Karger and Clifford Stein. A new approach to the minimum cut problem. J. ACM , 43(4):601--640, 1996

    work page 1996

  37. [37]

    Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

    Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians - fast, sparse, and simple. In FOCS , pages 573--582. IEEE Computer Society, 2016. Available at http://arxiv.org/abs/1605.02353

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  38. [38]

    Y. T. Lee, R. Peng, and D. A. Spielman. Sparsified cholesky solvers for SDD linear systems. CoRR , abs/1506.08204, 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  39. [39]

    Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems

    Yin Tat Lee and Aaron Sidford. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , FOCS '13, pages 147--156, Washington, DC, USA, 2013. IEEE Computer Society

    work page 2013

  40. [40]

    Y. T. Lee and A. Sidford. Path finding methods for linear programming: Solving linear programs in O ( vrank ) iterations and faster algorithms for maximum flow. In FOCS , 2014

    work page 2014

  41. [41]

    A survey of network flow applications

    Bingdong Li, Jeff Springer, George Bebis, and Mehmet Hadi Gunes. A survey of network flow applications. Journal of Network and Computer Applications , 36(2):567--581, 2013

    work page 2013

  42. [42]

    Fast Approximation Algorithms for Cut-based Problems in Undirected Graphs

    Aleksander Madry. Fast approximation algorithms for cut-based problems in undirected graphs. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages 245--254. IEEE, 2010. Available at http://arxiv.org/abs/1008.1975

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  43. [43]

    From graphs to matrices, and back: new techniques for graph algorithms

    Aleksander Madry. From graphs to matrices, and back: new techniques for graph algorithms . PhD thesis, Massachusetts Institute of Technology, 2011

    work page 2011

  44. [44]

    A. Madry. Navigating central path with electrical flows: From flows to matchings, and back. In FOCS , 2013

    work page 2013

  45. [45]

    Computing Maximum Flow with Augmenting Electrical Flows

    Aleksander Madry. 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 , pages 593--602, 2016. Available at: https://arxiv.org/abs/1608.06016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  46. [46]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming . Society for Industrial and Applied Mathematics, 1994

    work page 1994

  47. [47]

    James B. Orlin. 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 , pages 765--774, 2013

    work page 2013

  48. [48]

    Approximate Undirected Maximum Flows in O(m polylog(n)) Time

    Richard Peng. Approximate undirected maximum flows in O (m polylog (n)) time. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1862--1867. SIAM, 2016. Available at http://arxiv.org/abs/1411.7631

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  49. [49]

    An Efficient Parallel Solver for SDD Linear Systems

    Richard Peng and Daniel A. Spielman. An efficient parallel solver for SDD linear systems. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing , STOC '14, pages 333--342, New York, NY, USA, 2014. ACM. Available at http://arxiv.org/abs/1311.3286

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  50. [50]

    A survey of graph theoretical approaches to image segmentation

    Bo Peng, Lei Zhang, and David Zhang. A survey of graph theoretical approaches to image segmentation. Pattern Recognition , 46(3):1020--1038, 2013

    work page 2013

  51. [51]

    Nonlinear total variation based noise removal algorithms

    Leonid I Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena , 60(1-4):259--268, 1992

    work page 1992

  52. [52]

    Private Communication, 2019

    Sushant Sachdeva. Private Communication, 2019

    work page 2019

  53. [53]

    On the history of the transportation and maximum flow problems

    Alexander Schrijver. On the history of the transportation and maximum flow problems. Math. Program. , 91(3):437--445, 2002

    work page 2002

  54. [54]

    Nearly Maximum Flows in Nearly Linear Time

    Jonah Sherman. 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 , pages 263--269, 2013. Available at http://arxiv.org/abs/1304.2077

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  55. [55]

    Area-convexity, l\( _ \( \) \) regularization, and undirected multicommodity flow

    Jonah Sherman. 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 , pages 452--460, 2017

    work page 2017

  56. [56]

    Generalized Preconditioning and Network Flow Problems

    Jonah Sherman. Generalized preconditioning and undirected minimum-cost flow. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '17, pages 772--780, 2017. Available at: https://arxiv.org/abs/1606.07425

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  57. [57]

    D. A. Spielman. Conductance, the Normalized Laplacian, and Cheeger’s Inequality . http://www.cs.yale.edu/homes/spielman/561/lect11-18.pdf, 2018

    work page 2018

  58. [58]

    Graph Sparsification by Effective Resistances

    D. Spielman and N. Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing , 40(6):1913--1926, 2011. Available at http://arxiv.org/abs/0803.0929

    work page internal anchor Pith review Pith/arXiv arXiv 1913

  59. [59]

    A data structure for dynamic trees

    Daniel D Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of computer and system sciences , 26(3):362--391, 1983. Announced at STOC'81

    work page 1983

  60. [60]

    Self-adjusting binary search trees

    Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM , 32(3):652--686, 1985

    work page 1985

  61. [61]

    Spielman and S

    D. Spielman and S. Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications , 35(3):835--885, 2014. Available at http://arxiv.org/abs/cs/0607105

    work page arXiv 2014

  62. [62]

    Expander decomposition and pruning: Faster, stronger, and simpler, 2018

    Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler, 2018. To appear at SODA 2019. https://dw236.github.io/papers/main_decomp.pdf

    work page 2018

  63. [63]

    Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput. Math. , 12(4):389--434, August 2012. Available at http://arxiv.org/abs/1004.4389

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  64. [64]

    Duality-based algorithms for total-variation-regularized image restoration

    Mingqiang Zhu, Stephen J Wright, and Tony F Chan. Duality-based algorithms for total-variation-regularized image restoration. Computational Optimization and Applications , 47(3):377--400, 2010

    work page 2010