Abstract
Moss and Rabani [13] 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(logn)-approximation algorithm for the prize-collecting node-weighted Steiner tree problem (PCST)—where the goal is to minimize the cost of a tree plus the penalty of vertices not covered by the tree. They use the algorithm for PCST to obtain a bicriteria (2, O(logn))-approximation algorithm for the Budgeted node-weighted Steiner tree problem—where the goal is to maximize the prize of a tree with a given budget for its cost. Their solution may cost up to twice the budget, but collects a factor \(\Omega(\frac{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(logh)-approximation algorithm for a more general problem, prize-collecting node-weighted Steiner forest (PCSF), 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 [11] and Guha et al. [9]) leads to a much simpler algorithm than that of Moss and Rabani [13] for PCST.
Our second main contribution is for the Budgeted node-weighted Steiner tree problem, which is also an improvement to Moss and Rabani [13] and Guha et al. [9]. In the unrooted case, we improve upon an O(log2 n)-approximation of [9], and present an O(logn)-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 [13] to a bicriteria approximation ratio of (1 + ε, O(logn)/ε 2) for any positive (possibly subconstant) ε. That is, for any permissible budget violation 1 + ε, 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 [13].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized Steiner problem on networks. In: STOC (1991)
Chekuri, C., Ene, A., Vakilian, A.: Prize-collecting survivable network design in node-weighted graphs. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX/RANDOM 2012. LNCS, vol. 7408, pp. 98–109. Springer, Heidelberg (2012)
Cheng, X., Li, Y., Du, D.-Z., Ngo, H.Q.: Steiner trees in industry. In: Handbook of Combinatorial Optimization (2005)
Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Mathematical Programming 100, 411–421 (2004)
Erlebach, T., Grant, T., Kammer, F.: Maximising lifetime for fault-tolerant target coverage in sensor networks. In: SPAA (2011)
Feigenbaum, J., Papadimitriou, C.H., Shenker, S.: Sharing the cost of multicast transmissions. Journal of Computer and System Sciences 63, 21–41 (2001)
Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: STOC (2005)
Goemans, M., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. on Computing 24, 296–317 (1992)
Guha, S., Moss, A., Naor, J(S.), Schieber, B.: Efficient recovery from power outage. In: STOC (1999)
Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation. J. ACM
Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19(1), 104–115 (1995)
Könemann, J., Sadeghian, S., Sanita, L.: An LMP O(logn)-approximation algorithm for node weighted prize collecting Steiner tree (unpublished, 2013)
Moss, A., Rabani, Y.: Approximation algorithms for constrained node weighted Steiner tree problems. SIAM J. Comput. 37(2), 460–481 (2007)
Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees - short or small. SIAM J. Discrete Math. 9(2), 178–200 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bateni, M., Hajiaghayi, M., Liaghat, V. (2013). Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39206-1_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-39206-1_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39205-4
Online ISBN: 978-3-642-39206-1
eBook Packages: Computer ScienceComputer Science (R0)