算法返回的是几乎可行流，而非精确可行流
论文的定理 1.1 指出，在温和假设下，存在一个算法可以得到最小费用 k 商品流线性规划的一个几乎可行解，其目标值至多比该规划的最小值多 1/poly(n)。"几乎可行"有精确定义：顶点守恒残差满足 ‖Bᵀf_i − d_i‖∞ ≤ 1/poly(n)，其中 B 是 m×n 的有向边—顶点关联矩阵，d_i 是商品 i 的需求向量。
这一区分很重要，因为论文明确指出，在保持运行时间的前提下无法指望找到可行解。仅就两种商品而言，精确有向流经由一项被引为 [Ita78] 的归约，已具有与一般线性规划相同的多项式时间表达力。因此这里的保证是目标值与守恒性上各带 1/poly(n) 的加性误差，而非精确守恒。
问题本身被表述为一个线性规划：在每种商品流量 f_i 非负、每条边 e 上满足共享容量约束 f_1(e) + f_2(e) + ⋯ + f_k(e) ≤ 1、且对每种商品满足 Bᵀf_i = d_i 的条件下，最小化 cᵀ(f_1 + f_2 + ⋯ + f_k)。论文指出，共享费用向量与单位容量是此前最接近的运行时间界所用表述的一个特例。
原线性规划秩很高，秩敏感求解器代价高昂
一个自然的初步想法是直接把秩敏感线性规划算法用于最小费用 k 商品流线性规划。论文指出这样做代价高昂，因为该线性规划秩很高。论文讨论的秩敏感 box-LP 方法为每条边引入一个未使用容量变量，共 (k+1)m 个变量，等式秩恰为 m + k(n−q)，需要 Õ(√(m + k(n−q)) log(1/ε)) 轮自适应加权正规系统求解。
论文陈述的目标是降低稠密情形下的自适应求解次数。其路径是在不放松共享容量的前提下，把 m 个共享容量方程从线性系统中移除，方法是把可行的逐边转移通过所谓 zonotope 方法编码进去。
论文所做的比较对象，是可能为有向图上高精度最小费用多商品流最强的专用运行时间界，由 van den Brand 与 Zhang 给出。对于多项式量级的整数容量、费用与需求，且 ε⁻¹ ≤ poly(n)，该确定性算法运行时间为 Õ(k^{5/2}√m n^{ω−1/2})，执行 Õ(√(km) log(CU/ε)) 次顺序内点迭代，其中 C、U 界定数值数据。论文指出，就总运行时间比较而言这是最接近的结果，但它既不是精确守恒，也不是并行深度。
zonotope 流每次求解至少推进 1/k
核心机制是一次改写。给定当前一组 f_1, …, f_k 的取值，其费用已接近最小值，论文把问题改写为关于更新量 Δf_i 的形式，约束为 Δf_i(e) ≥ −f_i(e)、共享约束 Δf_1(e) + ⋯ + Δf_k(e) ≤ 1 − f_1(e) − ⋯ − f_k(e)，以及 BᵀΔf_i = 0。按 f_i ← f_i + Δf_i 更新即可还原一个等价问题。
算法在这一改写中插入一个新的线性规划，即 zonotope 流。它寻找整数 r ≥ k、系数 α ∈ R^{k×r}、容量向量 l_1, …, l_r 与 u_1, …, u_r ∈ R^m，以及常数 0 < λ ≤ 1。zonotope 线性规划在 l_j(e) ≤ x_j(e) ≤ u_j(e)（对所有 j 与 e）以及 Bᵀ Σ_j α_ij x_j = 0（对所有 i）的约束下，最小化 cᵀ Σ_i Σ_j α_ij x_j。顶点残差条件存在于经 αx 映射后的 k 种商品中，而容量存在于 r 种商品中。
需要满足两个性质。可行性指诱导出的 (Δf_1, …, Δf_k) 对更新问题是可行的。λ-有效性指 zonotope 线性规划的最小值至多为更新问题最小值的 λ 倍。论文给出满足两者且 λ = 1/k 的数据，因此求解 zonotope 线性规划至少推进 1/k 的进度。由于达到 1/poly(n) 加性误差只需 O(k log n) 个 zonotope 线性规划，总运行时间仍为 Õ(poly(k)(n^2.5 + m√n))。
名称来自几何。对每条边 e，可达的逐商品转移集合 K(e) 是一个超立方体的线性像，因此是一个 zonotope；而可行的更新区域 S(e) 是一个单纯形。可行性对应 K(e) ⊆ S(e) 对所有 e 成立，λ-有效性对应 λ·S(e) ⊆ K(e) 对所有 e 成立。
λ = 1/k 是该构造下的最优取值
论文包含一条说明，证明不存在同时满足两个包含关系且 λ > 1/k 的数据。论证是：所有 zonotope 在平移意义下都是中心对称凸体。若 λ > 1/k，包含关系 (1−λ)W + λΔ_k ⊆ K(W) ⊆ Δ_k 将意味着存在平移向量 v 使 −λΔ_k + v ⊆ Δ_k，而这是不可能的。
这使 λ = 1/k 的选取在该构造下最优，并直接决定必须求解的子问题数量。论文补充说，仍有可能通过使用更小的 λ 来减小 r，从而降低总运行时间——这是论文提出但未解决的方向。
显式构造取 r = (k+1 选 2)，把指标集 {1, …, r} 与数对 (μ, ν) 对应。对每条边 e，它取 W = (f_1(e), …, f_k(e), 1 − f_1(e) − ⋯ − f_k(e))，然后令 l_μν(e) = −(1/k)w_μ、u_μν(e) = (1/k)w_ν，并令 α_iμν 在 i = μ 时为 1、在 ν < k+1 且 i = ν 时为 −1、其余为 0。变量 ξ_μν 可理解为从商品 ν 取流并交给商品 μ，其中商品 k+1 代表未使用容量或空商品。
稀疏化正规系统才消除了矩阵乘法代价
运行时间依赖引理 4.1，它涉及一个线性规划：n ≤ m ≤ poly(n)，数据量级与条件数至多 poly(n)，矩阵 A 为 k 行稀疏。给定一个边距至少 1/poly(n) 的几乎可行初始点，它能在 Õ(n^{1/2}(km + k²n²)) 时间内找到几乎可行的 x，使 ‖Aᵀx − b‖₂ ≤ 1/poly(n) 且 cᵀx ≤ 1/poly(n) + OPT。论文指出这与一项先前定理相似，但证明不同，尤其不依赖矩阵乘法指数 ω。
证明运行一个仅用 Õ(√n) 次迭代的内点法，每次迭代需要求解形如 AᵀWAx = y 的系统，其中 W 为对角权重矩阵。目标是得到运行时间为 Õ(km + k²n²) 的 AᵀWA 求解器。直接套用一项近期线性系统结果会太慢，因为 AᵀA 一般是稠密的。算法改为按某个概率分布采样 A 的 Õ(n) 行来稀疏化 A，得到随机矩阵 Ã，使 ÃᵀÃ 在正半定意义下是 AᵀA 的 2-近似。关键在于 ÃᵀÃ 是稀疏的，只有 Õ(k²n) 个非零元。
采样使用杠杆分数 τ_i(A) = a_iᵀ(AᵀA)⁻¹a_i，它们落在 [0,1] 内且总和为 n。障碍在于朴素计算杠杆分数需要 AᵀA 的求解器——正是待解决的问题本身。论文采用迭代方法：在 A 下方追加 λ·I_n 定义 A_λ，从杠杆分数易于计算的 λ = poly(n) 出发，稀疏化，用预条件 Richardson 迭代得到 Aᵀ_{λ/2} 的求解器，再把 λ 减半。经过 Õ(1) 轮后 λ = 1/poly(n)，这些近似即可用于 τ_i(A)。
加速结论针对温和假设下的稠密图
运行时间 Õ(poly(k)(n^2.5 + m√n)) 针对含 n 个顶点、m 条边的有向图，并在论文的温和假设下成立：n ≤ m ≤ poly(n)、k ≤ n^{0.1}，以及 ‖c‖∞, ‖d_1‖∞, …, ‖d_k‖∞ ≤ poly(n)。k ≤ n^{0.1} 这一条件是对该界相对图规模所能覆盖商品数量的真实限制。
论文还指出，此类系统的解一般可以是有理数，其分子与分母有 Ω(n) 位数字，这会给任何算术运算带来 Ω(n) 倍的膨胀。这是问题本身的性质，而非该特定算法的缺陷，但它限定了此情形下"求解"可能意味着什么。
关于初始化，算法假设原问题有一个可行点。论文指出 0 对 zonotope 子问题必定是可行点，而要获得所需的 1/poly(n) 分离度，只需对 l 与 u 做轻微扰动，这意味着求解一个略有不同的问题，再把解扰动回原问题的几乎可行解。为获得原问题的初始可行点，它新建一个顶点 v*，并在 v* 与其余每个顶点之间加入容量与费用都非常大（poly(n) 量级）的边，从而保证存在满足所有顶点需求的流。
决定性比较在于自适应求解次数，而非仅看指数
论文对自身贡献的定位是：在不放松共享容量的前提下，把 m 个共享容量方程从线性系统中移除，从而降低稠密情形下的自适应求解次数。这正是它相对于秩敏感 box-LP 方法、以及相对于 van den Brand 与 Zhang 的界（执行 Õ(√(km) log(CU/ε)) 次顺序内点迭代）所定位的具体维度。
因此，对比较不同方法的读者而言，最具决策相关性的数字不只是 Õ(poly(k)(n^2.5 + m√n)) 这一总量，还在于它是通过 O(k log n) 次 zonotope 子问题求解、且不使用快速矩阵乘法实现的。不依赖 ω 这一点在引理 4.1 的证明中被明确陈述，摘要也重申算法不依赖任何快速矩阵乘法。
读者应权衡的取舍正是论文自己设定的：这是一个在目标值与守恒性上各带 1/poly(n) 加性误差的几乎可行解，换取的是避免矩阵乘法、减少自适应求解次数的稠密情形运行时间。当精确守恒或并行深度是硬性要求时，论文明确表示其结果两者皆非——因此在这套算法与先前界之间做选择，取决于具体实例能否接受加性守恒误差以及 k ≤ n^{0.1} 这一适用范围。
本文引用的文献
Faster high-accuracy multicommodity flow in dense graphs
构造一个低秩辅助线性规划（zonotope 流），其最小值至多为原最小费用 k 商品流最小值的 1/k，从而在含 n 个顶点、m 条边的有向图上以 Õ(poly(k)(n^2.5 + m√n)) 时间得到目标值与守恒性各带 1/poly(n) 加性误差的几乎可行解，且不使用快速矩阵乘法。