An Approximate Generalization of the Okamura-Seymour Theorem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910778972438528 |
|---|---|
| author | Kumar, Nikhil |
| author_facet | Kumar, Nikhil |
| contents | We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing $Ω(1)$-fraction of all the demands. To prove this, we give a $L_1$-embedding of the planar metric which approximately preserves distance between all pair of points on the same face. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_00795 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An Approximate Generalization of the Okamura-Seymour Theorem Kumar, Nikhil Discrete Mathematics Data Structures and Algorithms We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing $Ω(1)$-fraction of all the demands. To prove this, we give a $L_1$-embedding of the planar metric which approximately preserves distance between all pair of points on the same face. |
| title | An Approximate Generalization of the Okamura-Seymour Theorem |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2208.00795 |