{"id":"arxiv/2610.06665","url":"https://arxiv.org/abs/2610.06665","tags":["cs.DS","math.OC"],"score":0,"title":"Faster high-accuracy multicommodity flow in dense graphs","domain":"cs.DS","source":"arxiv","authors":["Chenxin Dai","Alicia Stepin","Colin Tang"],"reviews":0,"subject":"cs.DS","summary":"We give a fast algorithm for solving min-cost $k$-commodity flow. The basic idea is to construct an auxiliary linear program that has low rank and whose minimum value is at most $1/k$ times the minimum value of the original problem (thus, solving this auxiliary linear program will make at least $1/k$ fraction of progress in the original problem). Low-rank linear programs can be solved quickly using black-box techniques. Thus, our algorithm runs in time $\\tilde{O}(\\operatorname{poly}(k)(n^{2.5}+m\\sqrt{n}))$ on a directed graph with $n$ vertices and $m$ edges. We do not rely on any fast matrix…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{}}