Prize-Collecting Steiner Tree: A 1.79 Approximation

Prize-Collecting Steiner Tree (PCST) is a generalization of the Steiner Tree problem, a fundamental problem in computer science. In the classic Steiner Tree problem, we aim to connect a set of vertices known as terminals using the minimum-weight tree in a given weighted graph. In this generalized version, each vertex has a penalty, and there is flexibility to decide whether to connect each vertex or pay its associated penalty, making the problem more realistic and practical.

Both the Steiner Tree problem and its Prize-Collecting version had long-standing 2-approximation algorithms, matching the integrality gap of the natural LP formulations for both. This barrier for both problems has been surpassed, with algorithms achieving approximation factors below 2. While research on the Steiner Tree problem has led to a series of reductions in the approximation ratio below 2, culminating in a ln(4) + ǫ approximation by Byrka, Grandoni, Rothvoß, and Sanità [12], the Prize-Collecting version has not seen improvements in the past 15 years since the work of Archer, Bateni, Hajiaghayi, and Karloff [5, 6] (FOCS'09), which reduced the approximation factor for this problem from 2 to 1.9672. Interestingly, even the Prize-Collecting TSP approximation, which was first improved below 2 in the same paper, has seen several advancements since then (see, e.g., Blauth and Nägele [11] in STOC'23).

In this paper, we reduce the approximation factor for the PCST problem substantially to 1.7994 via a novel iterative approach.