Approximation algorithms for constrained node weighted Steiner tree problems

DOI10.1145/380752.380826zbMATH Open1323.68573OpenAlexW1974888782MaRDI QIDQ5175992FDOQ5175992

Authors: A. 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

Recommendations

• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• scientific article; zbMATH DE number 1445375
• A better approximation algorithm for the budget prize collecting tree problem.

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• The node-weighted steiner tree problem
• Variations of the prize‐collecting Steiner tree problem
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Title not available (Why is that?)
• Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
• Approximation algorithms for minimum weight partial connected set cover problem
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Balancing profits and costs on trees
• Approximating Steiner Networks with Node Weights
• Approximating some network design problems with node costs
• Title not available (Why is that?)
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Approximation schemes for node-weighted geometric Steiner tree problems
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175992)