EUVIMEDEUVIMED entdecken
Crossref

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

Phablo F. S. Moura

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →