Local Sherman's Algorithm for Multi-commodity Flow
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917915989639168 |
|---|---|
| author | Li, Jason Saranurak, Thatchaphol |
| author_facet | Li, Jason Saranurak, Thatchaphol |
| contents | We give the first local algorithm for computing multi-commodity flow and apply it to obtain a $(1+ε)$-approximate algorithm for computing a $k$-commodity flow on an expander with $m$ edges in $(m+ε^{-3}k^3D)n^{o(1)}$ time, where $D$ is the total demand. This is the first $(1+ε)$-approximate algorithm that breaks the $km$ multi-commodity flow barrier, albeit only on expanders. All previous algorithms either require $Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_10632 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local Sherman's Algorithm for Multi-commodity Flow Li, Jason Saranurak, Thatchaphol Data Structures and Algorithms We give the first local algorithm for computing multi-commodity flow and apply it to obtain a $(1+ε)$-approximate algorithm for computing a $k$-commodity flow on an expander with $m$ edges in $(m+ε^{-3}k^3D)n^{o(1)}$ time, where $D$ is the total demand. This is the first $(1+ε)$-approximate algorithm that breaks the $km$ multi-commodity flow barrier, albeit only on expanders. All previous algorithms either require $Ω(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. |
| title | Local Sherman's Algorithm for Multi-commodity Flow |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.10632 |