Low-Step Multi-Commodity Flow Emulators
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909228167331840 |
|---|---|
| author | Haeupler, Bernhard Hershkowitz, D Ellis Li, Jason Roeyskoe, Antti Saranurak, Thatchaphol |
| author_facet | Haeupler, Bernhard Hershkowitz, D Ellis Li, Jason Roeyskoe, Antti Saranurak, Thatchaphol |
| contents | We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous flow decomposition barrier for multi-commodity flow.
We prove the existence of low-step multi-commodity flow emulators and develop efficient algorithms to compute them. We then apply them to solve constant-approximate $k$-commodity flow in $O((m+k)^{1+ε})$ time. To bypass the $O(mk)$ flow decomposition barrier, we represent our output multi-commodity flow implicitly; prior to our work, even the existence of implicit constant-approximate multi-commodity flows of size $o(mk)$ was unknown.
Our results generalize to the minimum cost setting, where each edge has an associated cost and the multi-commodity flow must satisfy a cost budget. Our algorithms are also parallel. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_14384 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Low-Step Multi-Commodity Flow Emulators Haeupler, Bernhard Hershkowitz, D Ellis Li, Jason Roeyskoe, Antti Saranurak, Thatchaphol Data Structures and Algorithms We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flows whose paths contain a small number of edges, shattering the infamous flow decomposition barrier for multi-commodity flow. We prove the existence of low-step multi-commodity flow emulators and develop efficient algorithms to compute them. We then apply them to solve constant-approximate $k$-commodity flow in $O((m+k)^{1+ε})$ time. To bypass the $O(mk)$ flow decomposition barrier, we represent our output multi-commodity flow implicitly; prior to our work, even the existence of implicit constant-approximate multi-commodity flows of size $o(mk)$ was unknown. Our results generalize to the minimum cost setting, where each edge has an associated cost and the multi-commodity flow must satisfy a cost budget. Our algorithms are also parallel. |
| title | Low-Step Multi-Commodity Flow Emulators |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.14384 |