Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
<|reference_start|>Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem: 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 $(\alpha,\mu)$-approximation is possible, i.e., a solution that with budget $B+\alpha$ for all $B \in \mathbb{R}_{\geq 0}$ is a multiplicative $\mu$-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 $(\chi,1)$-approximation, where $\chi$ 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 $(\gamma,2)$-competitive where $\gamma$ 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 $(\gamma,3)$-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a $(3\chi,8)$-approximation and, more generally, a $\smash{\bigl((4\ell - 1)\chi, \frac{2^{\ell + 2}}{2^{\ell}-1}\bigr)}$-approximation for every fixed $\ell \in \mathbb{N}$.<|reference_end|>
@article{disser2024bicriterial,
    title={Bicriterial Approximation for the Incremental Prize-Collecting
  Steiner-Tree Problem},
    author={Yann Disser, Svenja M. Griesbach, Max Klimm, Annette Lutz},
    journal={arXiv preprint arXiv:2407.04447},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04447},
    primaryClass={cs.DS cs.DM}
}