Can min-cost k-commodity flow in dense graphs be solved faster with low-rank linear programs?

The algorithm returns an almost-feasible flow, not an exact one

The paper's Theorem 1.1 states that, under mild assumptions, there is an algorithm that obtains an almost-feasible solution to the min-cost k-commodity flow linear program whose value is at most 1/poly(n) plus the minimum value of that program. "Almost-feasible" is defined precisely: the vertex conservation residual satisfies ‖Bᵀf_i − d_i‖∞ ≤ 1/poly(n), where B is the m×n edge-vertex directed incidence matrix and d_i is the demand vector of commodity i.

This distinction matters because the paper explicitly says it cannot hope to find a feasible solution while preserving the runtime. Already for two commodities, exact directed flow has the same polynomial-time expressive power as general linear programming via a reduction cited as [Ita78]. So the guarantee here is an additive 1/poly(n) error in both objective value and conservation, not exact conservation.

The problem itself is stated as a linear program: minimize cᵀ(f_1 + f_2 + ⋯ + f_k) over nonnegative per-commodity flows f_i, subject to the shared capacity constraint f_1(e) + f_2(e) + ⋯ + f_k(e) ≤ 1 on every edge e, and subject to Bᵀf_i = d_i for each commodity. The shared cost vector and unit capacities are noted as a special case of the formulation used by the closest prior running-time bound.

The original LP has high rank, so rank-sensitive solvers are expensive

A natural first idea would be to apply rank-sensitive linear programming algorithms directly to the min-cost k-commodity flow LP. The paper says this proves expensive because the LP has high rank. The rank-sensitive box-LP method it discusses introduces one unused-capacity variable per edge, for a total of (k+1)m variables and equality rank exactly m + k(n−q), requiring Õ(√(m + k(n−q)) log(1/ε)) adaptive weighted normal-system rounds.

The paper's stated goal is to reduce the adaptive solve count in the dense regime. Its route is to remove the m shared-capacity equations from the linear systems without relaxing shared capacities, by encoding feasible edgewise transfers through what it calls the zonotope method.

The comparison the paper draws is with the strongest specialized running-time bound for high-accuracy minimum-cost multicommodity flow on possibly directed graphs, due to van den Brand and Zhang. For integer capacities, costs and demands of polynomial magnitude, and for ε⁻¹ ≤ poly(n), that deterministic algorithm runs in time Õ(k^{5/2}√m n^{ω−1/2}) and performs Õ(√(km) log(CU/ε)) sequential interior-point iterations, where C and U bound the numerical data. The paper notes this is the closest result for total-running-time comparison, but is neither exact-conservation nor parallel-depth.

A zonotope flow makes at least 1/k progress per solve

The core mechanism is a reformulation. Given a current assignment of f_1, …, f_k whose cost is close to the minimum, the paper rewrites the problem in terms of updates Δf_i, with constraints Δf_i(e) ≥ −f_i(e), the shared constraint Δf_1(e) + ⋯ + Δf_k(e) ≤ 1 − f_1(e) − ⋯ − f_k(e), and BᵀΔf_i = 0. Updating f_i ← f_i + Δf_i recovers an equivalent problem.

Into this reformulation the algorithm inserts a new linear program, the zonotope flow. It searches for an integer r ≥ k, coefficients α ∈ R^{k×r}, capacity vectors l_1, …, l_r and u_1, …, u_r ∈ R^m, and a constant 0 < λ ≤ 1. The zonotope LP minimizes cᵀ Σ_i Σ_j α_ij x_j subject to l_j(e) ≤ x_j(e) ≤ u_j(e) for all j and e, and Bᵀ Σ_j α_ij x_j = 0 for all i. The vertex residue conditions live in the k commodities mapped through αx, while the capacities live in the r commodities.

Two properties are required. Feasibility means the induced (Δf_1, …, Δf_k) is feasible for the update problem. λ-Efficacy means the minimum value of the zonotope LP is at most λ times the minimum of the update problem. The paper shows data satisfying both with λ = 1/k, so solving the zonotope LP makes at least a 1/k amount of progress. Because only O(k log n) zonotope linear programs are needed to reach 1/poly(n) additive error, the total runtime stays Õ(poly(k)(n^2.5 + m√n)).

The name comes from the geometry. For each edge e, the set K(e) of achievable commodity-wise transfers is a linear image of a hyperbox and therefore a zonotope, while the feasible update region S(e) is a simplex. Feasibility corresponds to K(e) ⊆ S(e) for all e, and λ-Efficacy to λ·S(e) ⊆ K(e) for all e.

λ = 1/k is optimal for this construction

The paper includes a note establishing that no data can satisfy both containment conditions with λ > 1/k. The argument is that all zonotopes are, up to translation, centrally symmetric convex bodies. If λ > 1/k, the containment (1−λ)W + λΔ_k ⊆ K(W) ⊆ Δ_k would imply −λΔ_k + v ⊆ Δ_k for some translation vector v, which is not possible.

This makes the choice of λ = 1/k optimal for this construction, and it directly determines the number of subproblems that must be solved. The paper adds that it may still be possible to reduce r by using a smaller value of λ, in such a way that the total runtime is reduced — a direction it raises rather than resolves.

The explicit construction sets r = (k+1 choose 2), identifying the index set {1, …, r} with pairs (μ, ν). For each edge e it sets W = (f_1(e), …, f_k(e), 1 − f_1(e) − ⋯ − f_k(e)), then l_μν(e) = −(1/k)w_μ, u_μν(e) = (1/k)w_ν, and α_iμν equal to 1 if i = μ, −1 if ν < k+1 and i = ν, and 0 otherwise. The variables ξ_μν can be read as taking flow from commodity ν and giving it to commodity μ, with commodity k+1 representing unused capacity or the null commodity.

Sparsifying the normal system is what removes the matrix-multiplication cost

The runtime rests on Lemma 4.1, which concerns a linear program with n ≤ m ≤ poly(n), data of magnitude and condition number at most poly(n), and a k-row-sparse matrix A. Given an almost-feasible initial point with margins at least 1/poly(n), it finds an almost-feasible x with ‖Aᵀx − b‖₂ ≤ 1/poly(n) and cᵀx ≤ 1/poly(n) + OPT in time Õ(n^{1/2}(km + k²n²)). The paper notes this is similar to a prior theorem but with a different proof and, in particular, no dependence on the matrix multiplication exponent ω.

The proof runs an interior-point method using only Õ(√n) iterations, each requiring a solve of a system AᵀWAx = y for a diagonal weight matrix W. The target is a solver for AᵀWA running in Õ(km + k²n²). A naive application of a recent linear-system result would be too slow because AᵀA is generally dense. Instead the algorithm sparsifies A by sampling Õ(n) of its rows according to a probability distribution, producing a random matrix à such that Ãᵀà is a 2-approximation to AᵀA in the positive semidefinite sense. The key point is that Ãᵀà is sparse, with only Õ(k²n) nonzero entries.

Sampling uses leverage scores τ_i(A) = a_iᵀ(AᵀA)⁻¹a_i, which lie in [0,1] and sum to n. The obstacle is that computing leverage scores naively requires a solver for AᵀA — the very problem being solved. The paper follows an iterative approach: define A_λ by appending λ·I_n below A, start with λ = poly(n) where leverage scores are easy to compute, sparsify, use preconditioned Richardson iteration to obtain a solver for Aᵀ_{λ/2}, and halve λ. After Õ(1) rounds, λ = 1/poly(n) and the approximations can be used for τ_i(A).

The speedup is stated for dense graphs under mild assumptions

The running time Õ(poly(k)(n^2.5 + m√n)) is stated for a directed graph with n vertices and m edges, and it holds under the paper's mild assumptions: n ≤ m ≤ poly(n), k ≤ n^{0.1}, and ‖c‖∞, ‖d_1‖∞, …, ‖d_k‖∞ ≤ poly(n). The k ≤ n^{0.1} condition is a real restriction on how many commodities the bound covers relative to graph size.

The paper also notes that in general the solution to such a system can be rational numbers whose numerator and denominator have Ω(n) digits, which incurs an Ω(n)-factor blowup of any arithmetic operations. That is a property of the problem, not a defect of this particular algorithm, but it bounds what "solving" can mean in this setting.

On initialization, the algorithm assumes a feasible point to the original problem. It notes that 0 is guaranteed to be a feasible point for the zonotope subproblem, and that to obtain the required 1/poly(n) separation one simply perturbs l and u slightly, which means solving a slightly different problem and then perturbing the solution back to an almost-feasible solution of the original. To obtain an initial feasible point for the original problem, it creates a new vertex v* and adds edges between v* and every other vertex with very large poly(n) capacities and costs, guaranteeing a flow that satisfies all vertex demands.

The decisive comparison is adaptive solve count, not just the exponent

The paper's own framing of its contribution is that it reduces the adaptive solve count in the dense regime by removing the m shared-capacity equations from the linear systems without relaxing shared capacities. That is the specific axis on which it positions itself against the rank-sensitive box-LP method and against the van den Brand and Zhang bound, which performs Õ(√(km) log(CU/ε)) sequential interior-point iterations.

The most decision-relevant number for a reader comparing approaches is therefore not only the Õ(poly(k)(n^2.5 + m√n)) total, but the fact that it is achieved with O(k log n) zonotope subproblem solves and with no fast matrix multiplication. The absence of an ω dependence is stated explicitly in the proof of Lemma 4.1, and the abstract repeats that the algorithm does not rely on any fast matrix multiplication.

The trade-off a reader should weigh is the one the paper itself sets up: this is an almost-feasible solution with additive 1/poly(n) error in both objective and conservation, in exchange for a dense-regime runtime that avoids matrix multiplication and reduces adaptive solves. Where exact conservation or parallel depth is the binding requirement, the paper states plainly that its result is neither — so the choice between this algorithm and the prior bound turns on whether additive conservation error and the k ≤ n^{0.1} regime are acceptable for the instance at hand.

Sources used in this answer