Primal‐Dual Bicriteria Approximation for A Constrained Prize‐Collecting Steiner Tree Problem

We address the Constrained Prize Collecting Steiner Tree problem ( cpst ), a bicriteria network design problem in which the objective is to minimize edge costs together with penalties for excluded vertices, subject to a budget constraint on a secondary edge weight. This problem generalizes the classical Prize Collecting Steiner Tree ( pst ) problem and arises naturally in budget‐limited network design applications. We show that cpst does not admit any polynomial‐time approximation algorithm that respects the budget constraint, unless . Motivated by this hardness result, we devise a ‐bicriteria approximation for cpst , that is, a polynomial‐time 4‐approximation which produces a tree of weight at most 4 times the budget. Our approach combines a Lagrangian relaxation of the budget constraint with the primal‐dual algorithm for pst , and employs a binary‐search procedure over the Lagrangian multiplier. The proposed algorithm improves upon the previously best known generic bicriteria approximation guarantee for cpst , which yields a ‐bicriteria approximation when applied to cpst with the current best approximation for pst .