Primal‐Dual Bicriteria Approximation for A Constrained Prize‐Collecting Steiner Tree Problem
Networks · 2026-12 · 88 (4) · 395-401
DOI: 10.1002/net.70061 ↗Kurz gefasst
Fachartikel in der Zeitschrift Networks, online erschienen am 15.07.2026. Verfasst von Phablo F. S. Moura. Die Arbeit nennt 20 Literaturangaben. Gefördert von: Onderzoeksraad, KU Leuven.
Abstract (Originalsprache)
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 .
Förderung
- Onderzoeksraad, KU Leuven
Zitieren
APA
Moura, P. F. S. (2026). Primal‐Dual Bicriteria Approximation for A Constrained Prize‐Collecting Steiner Tree Problem. Networks, 88(4), 395-401. https://doi.org/10.1002/net.70061
Vancouver
Moura PFS. Primal‐Dual Bicriteria Approximation for A Constrained Prize‐Collecting Steiner Tree Problem. Networks. 2026;88(4):395-401. doi:10.1002/net.70061
BibTeX
@article{Moura2026,
author = {Moura, Phablo F. S.},
title = {Primal‐Dual Bicriteria Approximation for A Constrained Prize‐Collecting Steiner Tree Problem},
journal = {Networks},
year = {2026},
volume = {88},
number = {4},
pages = {395--401},
doi = {10.1002/net.70061}
}
EUVIMED