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 (, ) -approximation is possible, i. e. , a solution that with budget B+ for all B R ₀ 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 ( (4 - 1), 2^{ + 22^{-1}) }-approximation for every fixed N.