Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
From MaRDI portal
Publication:3512450
DOI10.1007/978-3-540-69903-3_10zbMATH Open1155.68585OpenAlexW1571907562MaRDI QIDQ3512450FDOQ3512450
Authors: 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
Recommendations
- Bicriteria approximation tradeoff for the node-cost budget problem
- Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
- Approximation algorithms for constrained node weighted Steiner tree problems
- A better approximation algorithm for the budget prize collecting tree problem.
- Improved approximation algorithms for (budgeted) node-weighted Steiner problems
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- Bicriteria Network Design Problems
- The constrained minimum spanning tree problem
- Geometric algorithms and combinatorial optimization.
- A General Approximation Technique for Constrained Forest Problems
- The budgeted maximum coverage problem
- Efficient recovery from power outage (extended abstract)
- Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
- Title not available (Why is that?)
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
Cited In (2)
This page was built for publication: Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3512450)
