Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem

Abstract

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 $(\hat{I}\pm ,\hat{I}¼)$-approximation is possible, i.e., a solution that with budget $B+\hat{I}\pm$ for all $B\in {\mathbb{R}}_{\ge 0}$ is a multiplicative $\hat{I}¼$-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 $(\ddot{I}‡,1)$-approximation, where $\ddot{I}‡$ 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 $({\hat{I}}^3,2)$-competitive where ${\hat{I}}^3$ 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 $({\hat{I}}^3,3)$-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a $(3\ddot{I}‡,8)$-approximation and, more generally, a $((4\ell -1)\ddot{I}‡,\frac{2^{\ell +2}}{2^{\ell }-1})$-approximation for every fixed $\ell \in \mathbb{N}$.