Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem

DOI10.1007/978-3-540-69903-3_10zbMath1155.68585OpenAlexW1571907562MaRDI QIDQ3512450

Yuval Rabani, Gabriel Scalosub

Publication date: 15 July 2008

Published in: Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69903-3_10

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Geometric algorithms and combinatorial optimization.
• The budgeted maximum coverage problem
• Efficient recovery from power outage (extended abstract)
• A threshold of ln n for approximating set cover
• Saving an epsilon
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Bicriteria Network Design Problems
• A General Approximation Technique for Constrained Forest Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• The constrained minimum spanning tree problem
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems

This page was built for publication: Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem