Local Sherman's Algorithm for Multi-commodity Flow

Jason Li; Thatchaphol Saranurak

REVIEW 2 major objections 5 minor 21 references

Local Sherman's Algorithm for Multi-commodity Flow

T0 review · 2 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper gives the first local algorithm for multi-commodity flow, and on expander graphs it computes a (1+ε)-approximate flow in time that avoids the km barrier.

desk verdict The local multi-commodity flow algorithm is the real contribution; the expander application is a plausible but currently under-supported add-on, fixable with a pointer to CHS24 and a corrected runtime bound. read the letter →

arxiv 2501.10632 v2 pith:QA2RCIBV submitted 2025-01-18 cs.DS

Jason Li , Thatchaphol Saranurak This is my paper · ORCID

classification cs.DS MSC 68Q2568W4005C8590C35

keywords multi-commodityflowlocalalgorithmsexpandergraphsmultiplicativeweightsupdateSherman'salgorithmsublineartimecongestioninfeasibilitycertificate

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims to remove a long-standing bottleneck in multi-commodity flow: finding a (1+ε)-approximate routing of k commodities on an undirected graph used to require time proportional to k times the number of edges, because even writing down the answer could be that large. The authors give the first local algorithm for the problem: it reads only a sparse demand and runs in time depending on the demand size, not the whole graph. On expander graphs, the same technique yields a (1+ε)-approximate flow in about m plus a demand-dependent term, breaking the Ω(km) barrier for high-accuracy flow for the first time. The mechanism is to run Sherman's algorithm inside a multiplicative-weights loop while rounding every tiny weight to zero, so that each iteration touches only vertices with large cumulative imbalance.

What carries the argument

The engine is a localized version of Sherman's flow algorithm inside a Multiplicative Weights Update (MWU) loop. Each vertex maintains two nonnegative multiplicative weights, one for positive and one for negative potential, and each iteration routes unit flow along edges from higher to lower rounded potential. The rounding step zeroes every weight below $n$, so only vertices whose cumulative excess or deficit is at least $(\ln n)/\alpha$ keep nonzero potential and generate work; all other vertices behave as if their potential were zero, so no flow is sent between them. A refined MWU theorem (Theorem 2.3) shows that such additive approximation of the weights is harmless, while Lemma 2.7 charges the volume of active vertices to the input's $\ell^1$ norm, yielding the runtime bound. The expander application then calls a separate deterministic expander-routing theorem (Theorem 3.1), cited as implicit in [CHS24], to route the leftover residual demand with only $\varepsilon$ extra congestion.

What would settle it

The central claim would be refuted by any unit-capacity graph, $k$-commodity source function, and $\varepsilon$ for which the output flow leaves a vertex with residual demand exceeding $\varepsilon\deg(v)$, or for which the algorithm's runtime violates $O(\varepsilon^{-2}\log n(\|b\|_0+\varepsilon^{-1}\|b\|_1))$; a small path or cycle instance can be checked by simulating the stated update rule. The expander theorem would be refuted by exhibiting a $\varphi$-expander and a residual demand of the form Theorem 2.9 leaves behind that the cited expander-routing routine cannot route with congestion $\varepsilon$ in the claimed time.

Watch

Extended reading notes

Core claim

On a unit-capacity undirected graph $G=(V,E)$ with any $k$-commodity source function $b$, Theorem 2.9 gives an algorithm that, for error $\varepsilon \in (0,1)$, runs in $O(\varepsilon^{-2}\log n\,(\|b\|_0+\varepsilon^{-1}\|b\|_1))$ time and outputs either a certificate that the demand is infeasible or a feasible $k$-commodity flow whose residual demand at each vertex $v$ and commodity $j$ is at most $\varepsilon\deg(v)$. The application to expanders, Theorem 1.2, says that for a $\varphi$-expander with total demand $D=\sum_j d_j$, a flow of congestion $1+\varepsilon$ (or an infeasibility certificate) is computed in $(m+\varepsilon^{-3}k^3D)\cdot\mathrm{poly}(1/\varphi)\cdot 2^{O(\sqrt{\log n\log\log n})}$ time. The paper claims this is the first local multi-commodity flow algorithm and the first $(1+\varepsilon)$-approximate multi-commodity flow algorithm on expanders that avoids the $\Omega(km)$ time barrier.

Load-bearing premise

The expander result rests on the cited claim that any residual demand with per-vertex load at most $\alpha\deg(v)$ on a $\varphi$-expander can be routed with congestion $\alpha\,\mathrm{poly}(1/\varphi)2^{O(\sqrt{\log n\log\log n})}$ in near-linear time; if that cited expander-routing theorem is wrong or has different constants, Theorem 1.2's congestion and runtime do not follow.

Editorial extensions

If this is right

On any $\varphi$-expander, a $(1+\varepsilon)$-approximate $k$-commodity flow is computable in $(m+\varepsilon^{-3}k^3D)\cdot\mathrm{poly}(1/\varphi)\cdot 2^{O(\sqrt{\log n\log\log n})}$ time, with no factor of $km$.
Sparse demands, measured by $\|b\|_0$ and $\|b\|_1$, can be almost fully routed in sublinear time without reading the whole graph, and infeasibility is certified when the demand cannot be routed at all.
The rounded-weight MWU analysis applies to any MWU-based oracle whose per-round work is concentrated on the largest weights, so the localization trick is not limited to this specific flow algorithm.
Because the algorithm is deterministic and acknowledged by the paper to be immediately parallelizable, the same guarantee carries to settings where deterministic and low-depth algorithms are required.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next step, not pursued here, is to use the same weight-rounding idea to localize other iterative graph algorithms whose update rules are driven by multiplicative weights.
The runtime's dependence on $\|b\|_1$ rather than the size of the whole graph suggests the algorithm may be especially useful in dynamic and distributed settings where demands change locally; the paper does not develop this application.
The expander theorem's stated rate $(m+\varepsilon^{-3}k^3D)$ absorbs a separate $\varepsilon^{-2}k^3$ term that is only dominated when the total demand $D$ is not too small, so comparisons for very small $D$ should use the full derived expression.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Jason and Saranurak have a genuinely new result: the first local algorithm for multi-commodity flow, built on a clean observation that Sherman's MWU oracle can be run on rounded weights. The single- and multi-commodity proofs in Section 2 are careful, and the approximate-weights MWU theorem (2.3) is a real analytic contribution, not a restatement. The charging argument in Lemma 2.7 and its multi-commodity analogue are sound; I checked the edge-by-edge potential argument and it goes through. The infeasibility certificate for multi-commodity flow via the LP dual in Lemma 2.10 is also correct. So the core of the paper is in good shape.

The soft spots are real but manageable. The expander application, Theorem 1.2, depends entirely on Theorem 3.1, which is stated as 'implicit in [CHS24]' with no proof and no pointer to a specific lemma. That is not a cosmetic gap; Theorem 3.1 supplies both correctness and the poly(1/phi) 2^O(sqrt(log n log log n)) factors in the final runtime. The stated parameters--arbitrarily small alpha, weighted pairs, deterministic time (m+ell) poly--need to be verified against [CHS24]. This is likely a writing issue rather than a mathematical one, but it must be fixed before the paper is accepted.

Second, the runtime derivation in Section 3 drops the epsilon^{-2}k^3 term. After substituting tilde epsilon, the algorithm actually runs in time (m + epsilon^{-2} k^3 + epsilon^{-3} k^3 D) * poly, and the last line keeps only the epsilon^{-3} term. That is only dominated when D >= epsilon; for tiny total demand the stated bound is smaller than what is proven. The theorem should be restated with both terms, or the case D < epsilon handled separately. Minor but it makes Theorem 1.2 technically false as stated.

There are also typos in Lemma 2.2's definition of V_{

Overall: the local algorithm is a real advance and deserves a serious referee. The expander application is likely correct but needs the CHS24 dependency made explicit and the runtime bound fixed. I'd send it to review; the fixes are relatively small and the core contribution stands.

Referee Report

2 major / 5 minor

Summary. The paper proposes a local algorithm for multi-commodity flow on unit-capacity undirected graphs. The algorithm runs T = O(eps^-2 log n) rounds of multiplicative weights over vertex-commodity pairs; in each round it rounds all weights below n to zero, sends maximum-capacity flow along edges according to the resulting rounded potentials, and updates the weights from the per-vertex excesses. The main theorem, Theorem 2.9, states that in O(eps^-2 log n(||b||_0 + eps^-1 ||b||_1)) time the algorithm either produces a certificate that the k-commodity demand is infeasible or produces a feasible k-commodity flow whose residual demand at every vertex v and commodity j is at most eps deg(v). The paper then applies this to phi-expanders: by routing the residual demands with an expander-routing routine stated as 'implicit in [CHS24]' (Theorem 3.1), it claims a deterministic (1+eps)-approximation algorithm for k-commodity flow in (m + eps^-3 k^3 D) poly(1/phi) 2^{O(sqrt(log n log log n))} time, thereby breaking the km barrier on expanders.

Significance. The local-algorithm portion is an interesting and, on my reading, sound contribution. The charging argument in Lemmas 2.7 and 2.14 is careful, the approximate-MWU theorem (Theorem 2.3) is used correctly, and the infeasibility certificates are meaningful. I found no internal circularity in the MWU analysis: the guarantees are derived from the algorithm's own update rules rather than assumed. The rounding idea for multiplicative weights may well be reusable. If the expander application were fully justified, Theorem 1.2 would be a significant barrier result. However, the headline expander theorem currently rests on an unverified external theorem and on a runtime derivation that drops a non-negligible term, so the significance of the expander claim is conditional as written.

major comments (2)

[Section 3, Theorem 3.1] The entire expander application depends on Theorem 3.1, which is introduced with the sentence 'The following is implicit in [CHS24]' and is then used without a proof or a precise pointer to a theorem in that reference. This is load-bearing: Theorem 3.1 is the mechanism that turns the residual guarantees of Theorem 2.9 into a (1+eps)-congestion flow, and it supplies the poly(1/phi) 2^{O(sqrt(log n log log n))} factors in both the correctness and the running time of Theorem 1.2. As written, the reader cannot check whether the hypotheses and constants of the cited result match the needed statement (deterministic, arbitrary positive alpha, weighted demands, congestion alpha poly(1/phi) 2^{O(...)}, and time (m+ell) poly(1/phi) 2^{O(...)}). The proof of Theorem 1.2 should either include a proof of Theorem 3.1 or restate the exact theorem from [CHS24] and verify that it implies the stated form; otherwise Theorem 1.2 remains conditional on an unverified external claim.
[Section 3, proof of Theorem 1.2] The displayed derivation at the end of Section 3 contains the step (m + tilde-eps^-2 k + tilde-eps^-3 D) = (m + eps^-2 k^3 + eps^-3 k^3 D) = (m + eps^-3 k^3 D). The middle expression contains the term eps^-2 k^3, which is dropped without justification. This term is dominated by eps^-3 k^3 D only when D >= eps, and no such assumption appears in Theorem 1.2; it is also not necessarily dominated by m for the stated parameter range. Consequently, the claimed runtime in Theorem 1.2 is strictly smaller than the runtime established by the proof. The theorem should state the bound with the additional eps^-2 k^3 term, or the missing dominance assumption should be stated and justified.

minor comments (5)

[Lemma 2.2] The definition of V_<x should be {v : tilde-phi^i_v < x}; the text as printed uses '>' in both definitions.
[Lemma 2.11] The assumption is written as b_j(v) <= deg(v), but the proof and the sentence before the lemma require |b_j(v)| <= deg(v). The certificate returned when this check fails should also be specified; a single-commodity cut {v} with |b_j(v)| > deg(v) suffices.
[Theorem 2.3] The parameter nu is declared in the statement of Theorem 2.3 but is never used; either remove it or indicate its intended role.
[Section 3, residual decomposition] After decomposing r_j into weighted pairs, the expression sum_{i in [ell_j]} d_{j,ell_j} should be sum_{i in [ell_j]} d_{j,i}.
[Section 3, call to Theorem 3.1] The reduction says a greedy decomposition achieves ell_j <= ||r_j||_0, but it should also state explicitly that the decomposition can be chosen so that the total incident demand at each vertex v is |r_j(v)|; this is what justifies the parameter alpha = k tilde-eps in the call to Theorem 3.1.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the local MWU derivation is self-contained; the only load-bearing external theorem is from a disjoint author set, and remaining issues are verification and runtime-domination, not self-reference.

full rationale

The paper's derivation chain is not circular. Theorem 2.9 is proved from the algorithm's own MWU update rules: the approximate-weight MWU lemma (Theorem 2.3) is stated and proved, and Lemmas 2.4/2.11 and 2.5/2.12 verify its hypotheses from the definition of the rounded flow and the stopping rule, so the residual bound |r_j(v)| <= eps deg(v) is a derived guarantee, not an assumed or fitted target. Lemma 2.10 derives the infeasibility certificate from the LP weighting and the algorithm's own termination condition, again without presupposing the conclusion. The expander application composes Theorem 2.9 with Theorem 3.1, stated as 'The following is implicit in [CHS24]' and attributed to Chang, Huang, and Su, whose authors do not overlap with the present paper; therefore no load-bearing self-citation chain is present, and the explicitly stated theorem supplies independent content. Parameters such as alpha = eps/5 and T = Theta(eps^{-2} log n) are set by the proof, not calibrated to data. Two non-circular soft spots should nevertheless be flagged: (i) Theorem 3.1 is neither proved nor located in [CHS24], so Theorem 1.2 rests on an unverified external statement, a correctness/verifiability risk rather than circularity; (ii) the final display drops the eps^{-2}k^3 term by writing equality with eps^{-3}k^3D, which requires D >= eps, so for tiny total demand the stated bound is stronger than the proven one. Neither issue involves definitional equivalence, fitted parameters renamed as predictions, or self-citation as the load-bearing justification.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim depends on the expander routing theorem of [CHS24], the unit-capacity model, and the degree-normalized constraints. Algorithm parameters alpha, T, and the rounding threshold are set by the proof, not fitted to data.

free parameters (3)

alpha = epsilon/5
MWU step size; chosen so the average gain bound 5alpha translates to the per-vertex residual error bound epsilon deg(v).
T = Theta(alpha^{-2} log n)
Number of MWU rounds; set by the convergence requirement of Theorem 2.3.
Rounding threshold for zeroing weights = n
Weights below n are rounded to zero; this sparsifies the active vertex set A_i and is set so that ||w - w~||_inf <= n = |J|^{O(1)}, keeping the MWU error analysis intact.

assumptions (4)

domain assumption Theorem 3.1 (Expander Routing) is correct and has the stated parameters
Section 3 uses it to route residual demands with congestion alpha poly(1/phi) 2^{O(sqrt(log n log log n))}. It is stated as implicit in [CHS24] and not proven here, so Theorem 1.2 inherits any error in it.
domain assumption All edges have unit capacity
Lemmas 2.8 and 2.15 bound the local work by deg(v) on a unit-capacity graph; the paper notes this is the only place unit capacity is needed.
domain assumption The input satisfies |b_j(v)| <= deg(v) for all v and j
Lemmas 2.4 and 2.11 assume it; if violated, the algorithm outputs a single-vertex certificate of infeasibility, so it is without loss.
domain assumption G is a phi-expander in Theorem 1.2
The expander condition delta_S >= phi min(vol(S), vol(V \ S)) is used to apply Theorem 3.1 and to justify the degree cuts as a congestion approximator in Section 2's opening.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Local Sherman's Algorithm for Multi-commodity Flow." pith.science (2026). https://pith.science/paper/QA2RCIBV

@misc{pith2026250110632,
  author       = {Pith},
  title        = {Pith review of: Local Sherman's Algorithm for Multi-commodity Flow},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QA2RCIBV}},
  note         = {Machine review of arXiv:2501.10632}
}

abstract

We give the first local algorithm for computing multi-commodity flow and apply it to obtain a $(1+\epsilon)$-approximate algorithm for computing a $k$-commodity flow on an expander with $m$ edges in $(m+\epsilon^{-3}k^3D)n^{o(1)}$ time, where $D$ is the total demand. This is the first $(1+\epsilon)$-approximate algorithm that breaks the $km$ multi-commodity flow barrier, albeit only on expanders. All previous algorithms either require $\Omega(km)$ time or a big constant approximation. Our approach is by localizing Sherman's flow algorithm when put into the Multiplicative Weight Update (MWU) framework. We show that, on each round of MWU, the oracle could instead work with the *rounded weights* where all polynomially small weights are rounded to zero. Since there are only few large weights, one can implement the oracle call with respect to the rounded weights in sublinear time. This insight is generic and may be of independent interest.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 18 canonical work pages

[1]

Italiano, Veronika Loitzenbauer, and Nikos Parotsidis

Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, and Nikos Parotsidis. Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, Janua...

work page 2017
[2]

Deterministic Expander Routing: Faster and More Versatile

Yi-Jun Chang, Shang-En Huang, and Hsin-Hao Su. Deterministic expander routing: Faster and more versatile. arXiv preprint arXiv:2405.03908 , 2024

work page Pith review arXiv 2024
[3]

Maximum flow and minimum-cost flow in almost-linear time

Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. March 2022

work page 2022
[4]

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 forty-third annual ACM symposium on Theory of computing , pages 273--282, 2011

work page 2011
[5]

Parallel and distributed expander decomposition: Simple, fast, and near-optimal

Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Parallel and distributed expander decomposition: Simple, fast, and near-optimal. arXiv preprint arXiv:2410.13451 , 2024

arXiv 2024
[6]

Algorithm for solution of a problem of maximum flow in networks with power estimation

Yefim Dinitz. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Doklady , 11:1227--1280, 1970

work page 1970
[7]

Two-commodity flow is equivalent to linear programming under nearly-linear time reductions

Ming Ding, Rasmus Kyng, and Peng Zhang. Two-commodity flow is equivalent to linear programming under nearly-linear time reductions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2022

work page 2022
[8]

Maximal flow through a network

Lester R Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian journal of Mathematics , 8(3):399--404, 1956

work page 1956

Show all 21 references

[9]

Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms

Sebastian Forster, Danupon Nanongkai, Thatchaphol Saranurak, Liu Yang, and Sorrachai Yingchareonthawornchai. Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms. In SODA , pages 2046--2065. SIAM , 2020

2020
[10]

Goldberg and Satish Rao

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

1998
[11]

Low-step multi-commodity flow emulators

Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Roeyskoe, and Thatchaphol Saranurak. Low-step multi-commodity flow emulators. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 71--82, 2024

2024
[12]

Dynamic deterministic constant-approximate distance oracles with n^ worst-case update time

Bernhard Haeupler, Yaowei Long, and Thatchaphol Saranurak. Dynamic deterministic constant-approximate distance oracles with n^ worst-case update time. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024 , pages 203...

2024
[13]

Local flow partitioning for faster edge connectivity

Monika Henzinger, Satish Rao, and Di Wang. Local flow partitioning for faster edge connectivity. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 1919--1938, 2017

2017
[14]

Liu and Aaron Sidford

Yang P. Liu and Aaron Sidford. Faster energy maximization for faster maximum flow. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chic...

2020
[15]

Breaking quadratic time for small vertex connectivity and an approximation scheme

Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Breaking quadratic time for small vertex connectivity and an approximation scheme. In STOC , pages 241--252. ACM , 2019

2019
[16]

Flow-based algorithms for local graph clustering

Lorenzo Orecchia and Zeyuan Allen Zhu. Flow-based algorithms for local graph clustering. In SODA , pages 1267--1286. SIAM , 2014

2014
[17]

Nearly maximum flows in nearly linear time

Jonah Sherman. Nearly maximum flows in nearly linear time. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science , pages 263--269. IEEE, 2013

2013
[18]

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

2017
[19]

Expander decomposition and pruning: Faster, stronger, and simpler

Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. 2019. To appear in SODA'19

2019
[20]

A deterministic almost-linear time algorithm for minimum-cost flow

Jan Van Den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)...

2023
[21]

Faster high accuracy multi-commodity flow from single-commodity techniques

Jan van Den Brand and Daniel J Zhang. Faster high accuracy multi-commodity flow from single-commodity techniques. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 493--502. IEEE, 2023

2023

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Italiano, Veronika Loitzenbauer, and Nikos Parotsidis

Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, and Nikos Parotsidis. Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, Janua...

work page 2017

[2] [2]

Deterministic Expander Routing: Faster and More Versatile

Yi-Jun Chang, Shang-En Huang, and Hsin-Hao Su. Deterministic expander routing: Faster and more versatile. arXiv preprint arXiv:2405.03908 , 2024

work page Pith review arXiv 2024

[3] [3]

Maximum flow and minimum-cost flow in almost-linear time

Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. March 2022

work page 2022

[4] [4]

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 forty-third annual ACM symposium on Theory of computing , pages 273--282, 2011

work page 2011

[5] [5]

Parallel and distributed expander decomposition: Simple, fast, and near-optimal

Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Parallel and distributed expander decomposition: Simple, fast, and near-optimal. arXiv preprint arXiv:2410.13451 , 2024

arXiv 2024

[6] [6]

Algorithm for solution of a problem of maximum flow in networks with power estimation

Yefim Dinitz. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Doklady , 11:1227--1280, 1970

work page 1970

[7] [7]

Two-commodity flow is equivalent to linear programming under nearly-linear time reductions

Ming Ding, Rasmus Kyng, and Peng Zhang. Two-commodity flow is equivalent to linear programming under nearly-linear time reductions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2022

work page 2022

[8] [8]

Maximal flow through a network

Lester R Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian journal of Mathematics , 8(3):399--404, 1956

work page 1956