Lower Bounds on $0$-Extension with Steiner Nodes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911759818817536 |
|---|---|
| author | Chen, Yu Tan, Zihan |
| author_facet | Chen, Yu Tan, Zihan |
| contents | In the $0$-Extension problem, we are given an edge-weighted graph $G=(V,E,c)$, a set $T\subseteq V$ of its vertices called terminals, and a semi-metric $D$ over $T$, and the goal is to find an assignment $f$ of each non-terminal vertex to a terminal, minimizing the sum, over all edges $(u,v)\in E$, the product of the edge weight $c(u,v)$ and the distance $D(f(u),f(v))$ between the terminals that $u,v$ are mapped to. Current best approximation algorithms on $0$-Extension are based on rounding a linear programming relaxation called the \emph{semi-metric LP relaxation}. The integrality gap of this LP, with best upper bound $O(\log |T|/\log\log |T|)$ and best lower bound $Ω((\log |T|)^{2/3})$, has been shown to be closely related to the best quality of cut and flow vertex sparsifiers.
We study a variant of the $0$-Extension problem where Steiner vertices are allowed. Specifically, we focus on the integrality gap of the same semi-metric LP relaxation to this new problem. Following from previous work, this new integrality gap turns out to be closely related to the quality achievable by cut/flow vertex sparsifiers with Steiner nodes, a major open problem in graph compression. Our main result is that the new integrality gap stays superconstant $Ω(\log\log |T|)$ even if we allow a super-linear $O(|T|\log^{1-\varepsilon}|T|)$ number of Steiner nodes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09585 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower Bounds on $0$-Extension with Steiner Nodes Chen, Yu Tan, Zihan Data Structures and Algorithms In the $0$-Extension problem, we are given an edge-weighted graph $G=(V,E,c)$, a set $T\subseteq V$ of its vertices called terminals, and a semi-metric $D$ over $T$, and the goal is to find an assignment $f$ of each non-terminal vertex to a terminal, minimizing the sum, over all edges $(u,v)\in E$, the product of the edge weight $c(u,v)$ and the distance $D(f(u),f(v))$ between the terminals that $u,v$ are mapped to. Current best approximation algorithms on $0$-Extension are based on rounding a linear programming relaxation called the \emph{semi-metric LP relaxation}. The integrality gap of this LP, with best upper bound $O(\log |T|/\log\log |T|)$ and best lower bound $Ω((\log |T|)^{2/3})$, has been shown to be closely related to the best quality of cut and flow vertex sparsifiers. We study a variant of the $0$-Extension problem where Steiner vertices are allowed. Specifically, we focus on the integrality gap of the same semi-metric LP relaxation to this new problem. Following from previous work, this new integrality gap turns out to be closely related to the quality achievable by cut/flow vertex sparsifiers with Steiner nodes, a major open problem in graph compression. Our main result is that the new integrality gap stays superconstant $Ω(\log\log |T|)$ even if we allow a super-linear $O(|T|\log^{1-\varepsilon}|T|)$ number of Steiner nodes. |
| title | Lower Bounds on $0$-Extension with Steiner Nodes |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.09585 |