Approximation algorithms for constrained for constrained node weighted steiner tree problems

DOI10.1145/380752.380826zbMath1323.68573OpenAlexW1974888782MaRDI QIDQ5175992

Anna Moss, Yuval Rabani

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380826

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

Approximation schemes for node-weighted geometric Steiner tree problems ⋮ Approximating some network design problems with node costs ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ Approximating Steiner Networks with Node Weights ⋮ Variations of the prize‐collecting Steiner tree problem ⋮ Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Approximation algorithms for constrained for constrained node weighted steiner tree problems