On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908585340960768 |
|---|---|
| author | Laekhanukit, Bundit |
| author_facet | Laekhanukit, Bundit |
| contents | The Directed Steiner Tree (DST) problem is defined on a directed graph $G=(V,E)$, where we are given a designated root vertex $r$ and a set of $k$ terminals $K \subseteq V \setminus {r}$. The goal is to find a minimum-cost subgraph that provides directed $r \rightarrow t$ paths for all terminals $t \in K$.
The approximability of DST has long been a central open problem in network design. While there exist polylogarithmic-approximation algorithms with quasi-polynomial running times (Charikar et al. 1998; Grandoni, Laekhanukit, and Li 2019; Ghuge and Nagarajan 2020), the best known polynomial-time approximation until now has remained at $k^ε$, for any constant $ε> 0$. Whether a polynomial-time algorithm achieving a polylogarithmic approximation exists has remained unresolved.
In this paper, we present a flow-based LP-relaxation for DST that admits a polylogarithmic integrality gap under the relative integral condition -- there exists a fractional solution in which each edge $e$ either carries a zero flow ($f^t_e=0$) or uses its full capacity ($f^t_e=x_e$), where $f^t_e$ denotes the flow variable and $x_e$ denotes the indicator variable treated as capacities. This stands in contrast to known lower bounds, as the standard flow-based relaxation is known to exhibit a polynomial integrality gap even under relatively integral solutions. In fact, this relatively integral property is shared by all the known integrality gap instances of DST [Halperin~et~al., SODA'07; Zosin-Khuller, SODA'02; Li-Laekhanukit, SODA'22].
We further provide a randomized polynomial-time algorithm that gives an $O(\log^3 k)$-approximation, assuming access to a relatively integral fractional solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_10744 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions Laekhanukit, Bundit Data Structures and Algorithms Discrete Mathematics 68Q25, 68R10, 90C35 F.2.2; G.2.2 The Directed Steiner Tree (DST) problem is defined on a directed graph $G=(V,E)$, where we are given a designated root vertex $r$ and a set of $k$ terminals $K \subseteq V \setminus {r}$. The goal is to find a minimum-cost subgraph that provides directed $r \rightarrow t$ paths for all terminals $t \in K$. The approximability of DST has long been a central open problem in network design. While there exist polylogarithmic-approximation algorithms with quasi-polynomial running times (Charikar et al. 1998; Grandoni, Laekhanukit, and Li 2019; Ghuge and Nagarajan 2020), the best known polynomial-time approximation until now has remained at $k^ε$, for any constant $ε> 0$. Whether a polynomial-time algorithm achieving a polylogarithmic approximation exists has remained unresolved. In this paper, we present a flow-based LP-relaxation for DST that admits a polylogarithmic integrality gap under the relative integral condition -- there exists a fractional solution in which each edge $e$ either carries a zero flow ($f^t_e=0$) or uses its full capacity ($f^t_e=x_e$), where $f^t_e$ denotes the flow variable and $x_e$ denotes the indicator variable treated as capacities. This stands in contrast to known lower bounds, as the standard flow-based relaxation is known to exhibit a polynomial integrality gap even under relatively integral solutions. In fact, this relatively integral property is shared by all the known integrality gap instances of DST [Halperin~et~al., SODA'07; Zosin-Khuller, SODA'02; Li-Laekhanukit, SODA'22]. We further provide a randomized polynomial-time algorithm that gives an $O(\log^3 k)$-approximation, assuming access to a relatively integral fractional solution. |
| title | On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions |
| topic | Data Structures and Algorithms Discrete Mathematics 68Q25, 68R10, 90C35 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2412.10744 |