arXiv preprint ·
Faster high-accuracy multicommodity flow in dense graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 multiplication.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
Preserving Unstable Modes Through Inverse Dynamics in JEPA World Models
Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices
A Neural JKO Scheme for Hellinger-Kantorovich Gradient Flows via Monge-Growth Pairs
Structural Foundations of Nonlinear Systems with Unknown Inputs: The UID-Induced Normal Form and Minimal-Sensing Structure-from-Motion
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.