Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem

DOI10.1007/978-3-540-69903-3_10MaRDI QIDQ3512450zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A threshold of ln n for approximating set cover
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Efficient recovery from power outage (extended abstract)
• Geometric algorithms and combinatorial optimization.
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• The budgeted maximum coverage problem
• The constrained minimum spanning tree problem
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema

Cited in

(2)

• Approximate maxima finding of continuous functions under restricted budget (extended abstract)
• Bicriteria approximation tradeoff for the node-cost budget problem

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)