Improved approximation algorithms for (budgeted) node-weighted Steiner problems

DOI10.1007/978-3-642-39206-1_8zbMATH Open1336.68288arXiv1304.7530OpenAlexW1497634048MaRDI QIDQ5326552FDOQ5326552

Authors: MohammadHossein Bateni, Vahid Liaghat, Mohammad T. Hajiaghayi 

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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].

Full work available at URL: https://arxiv.org/abs/1304.7530

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.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cited In (16)

• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• 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.
• An approximation algorithm for maximum weight budgeted connected set cover
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Title not available (Why is that?)
• The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights
• Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
• Approximating node-weighted \(k\)-MST on planar graphs
• Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph
• A simple approximation algorithm for minimum weight partial connected set cover
• Covering problems in edge- and node-weighted graphs
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Approximation algorithms for constrained node weighted Steiner 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)