Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
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_ | 1866910514995527680 |
|---|---|
| author | Disser, Yann Griesbach, Svenja M. Klimm, Max Lutz, Annette |
| author_facet | Disser, Yann Griesbach, Svenja M. Klimm, Max Lutz, Annette |
| contents | We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial $(α,μ)$-approximation is possible, i.e., a solution that with budget $B+α$ for all $B \in \mathbb{R}_{\geq 0}$ is a multiplicative $μ$-approximation compared to the optimum solution with budget $B$. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a $(χ,1)$-approximation, where $χ$ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is $(γ,2)$-competitive where $γ$ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a $(γ,3)$-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a $(3χ,8)$-approximation and, more generally, a $\smash{\bigl((4\ell - 1)χ, \frac{2^{\ell + 2}}{2^{\ell}-1}\bigr)}$-approximation for every fixed $\ell \in \mathbb{N}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04447 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem Disser, Yann Griesbach, Svenja M. Klimm, Max Lutz, Annette Data Structures and Algorithms Discrete Mathematics We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial $(α,μ)$-approximation is possible, i.e., a solution that with budget $B+α$ for all $B \in \mathbb{R}_{\geq 0}$ is a multiplicative $μ$-approximation compared to the optimum solution with budget $B$. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a $(χ,1)$-approximation, where $χ$ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is $(γ,2)$-competitive where $γ$ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a $(γ,3)$-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a $(3χ,8)$-approximation and, more generally, a $\smash{\bigl((4\ell - 1)χ, \frac{2^{\ell + 2}}{2^{\ell}-1}\bigr)}$-approximation for every fixed $\ell \in \mathbb{N}$. |
| title | Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2407.04447 |