Improved approximation algorithms for (budgeted) node-weighted Steiner problems
From MaRDI portal
Publication:5326552
Abstract: Moss and Rabani[12] study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an O(log n)-approximation algorithm for the prize-collecting node-weighted Steiner tree problem (PCST). They use the algorithm for PCST to obtain a bicriteria (2, O(log n))-approximation algorithm for the Budgeted node-weighted Steiner tree problem. Their solution may cost up to twice the budget, but collects a factor Omega(1/log n) of the optimal prize. We improve these results from at least two aspects. Our first main result is a primal-dual O(log h)-approximation algorithm for a more general problem, prize-collecting node-weighted Steiner forest, where we have (h) demands each requesting the connectivity of a pair of vertices. Our algorithm can be seen as a greedy algorithm which reduces the number of demands by choosing a structure with minimum cost-to-reduction ratio. This natural style of argument (also used by Klein and Ravi[10] and Guha et al.[8]) leads to a much simpler algorithm than that of Moss and Rabani[12] for PCST. Our second main contribution is for the Budgeted node-weighted Steiner tree problem, which is also an improvement to [12] and [8]. In the unrooted case, we improve upon an O(log^2(n))-approximation of [8], and present an O(log n)-approximation algorithm without any budget violation. For the rooted case, where a specified vertex has to appear in the solution tree, we improve the bicriteria result of [12] to a bicriteria approximation ratio of (1+eps, O(log n)/(eps^2)) for any positive (possibly subconstant) (eps). That is, for any permissible budget violation (1+eps), we present an algorithm achieving a tradeoff in the guarantee for prize. Indeed, we show that this is almost tight for the natural linear-programming relaxation used by us as well as in [12].
Recommendations
- Improved approximation algorithms for (budgeted) node-weighted Steiner problems
- Approximation algorithms for constrained node weighted Steiner tree problems
- Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
- scientific article; zbMATH DE number 1445375
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
Cited in
(16)- Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
- Improved approximation algorithms for (budgeted) node-weighted Steiner problems
- Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
- An approximation algorithm for maximum weight budgeted connected set cover
- The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights
- Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph
- scientific article; zbMATH DE number 1445375 (Why is no real title available?)
- A simple approximation algorithm for minimum weight partial connected set cover
- Spider covering algorithms for network design problems
- Bicriteria approximation tradeoff for the node-cost budget problem
- A better approximation algorithm for the budget prize collecting tree problem.
- Approximation algorithms for constrained node weighted Steiner tree problems
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Approximating node-weighted \(k\)-MST on planar graphs
- Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
- Erratum to “Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems”
This page was built for publication: Improved approximation algorithms for (budgeted) node-weighted Steiner problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326552)
