Abstract
We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T ⊆ V including a particular vertex s called the root, and an integer k ≤ |T|. There are two cost functions on the edges of G, a buy cost \(b:E\longrightarrow {\mathbb{R}}^+\) and a distance cost \(r:E\longrightarrow {\mathbb{R}}^+\). The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑\(_{e\in{\it H}}\) b(e)+∑\(_{t\in{\it T}-{\it s}}\) dist(t,s) is minimize, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log4 n)-approximation for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e) over the edges, and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(logn),O(log3 n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least \(\frac{k}{8}\) terminals. Using this we obtain an (O(log2 n),O(log4 n))-approximation for the shallow-light k-Steiner tree and an O(log4 n)-approximation for the buy-at-bulk k-Steiner tree problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andrews, M.: Hardness of Buy-at-Bulk Network Design. In: Proceedings of FOCS 2004, pp. 115–124 (2004)
Andrews, M., Zhang, L.: Approximation algorithms for access network design. Algorithmica 34(2), 197–215 (2002)
Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: Proceedings of FOCS 1997, pp. 542–547 (1997)
Awerbuch, B., Azar, Y., Blum, A., Vempala, S.: New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Computing 28(1), 254–262 (1999)
Bar-Ilan, J., Kortsarz, G., Peleg, D.: Generalized submodular cover problems and applications. Theoretical Computer Science 250, 179–200 (2001)
Bartal, Y.: On approximating arbitrary matrices by tree metrics. In: Proceedings of STOC, pp. 161–168 (1998)
Blum, A., Ravi, R., Vempala, S.: A constant-factor approximation algorithm for the k MST problem (extended abstract). In: Proceedings of STOC 1996, pp. 442–448 (1996)
Charikar, M., Karagiozova, A.: On non-uniform multicommodity buy-at-bulk network design. In: Proceedings of STOC 2005, pp. 176–182 (2005)
Chekuri, C., Khanna, S., Naor, J.: A deterministic algorithm for the cost-distance problem. In: Proceedings of SODA 2001, pp. 232–233 (2001)
Chuzhoy, J., Gupta, A., Naor, J., Sinha, A.: On the approximability of some network design problems. In: Proceedings of SODA 2005, pp. 943–951 (2005)
Chekuri, C., Hajiaghayi, M., Kortsarz, G., Salavatipour, M.: Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems (submitted, 2006)
Cheriyan, J., Salman, F.S., Ravi, R., Subramanian, S.: Buy-at-bulk network design: Approximating the single-sink edge installation problem. SIAM Journal on Optimization 11(3), 595–610 (2000)
Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences 69(3), 485–497 (2004)
Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica 29(3), 410–421 (2001)
Garg, N.: A 3-Approximation for the minimum tree spanning k vertices. In: Proceedings FOCS 1996, pp. 302–309 (1996)
Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of STOC 2005, pp. 396–402 (2005)
Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problems. In: Proceedings of STOC 2001, pp. 383–388 (2001)
Guha, S., Meyerson, A., Munagala, K.: Hierarchical placement and network design problems. In: Proceedings of FOCS 2001, pp. 603–612 (2001)
Gupta, A., Kumar, A., Pal, M., Roughgarden, T.: Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. In: Proceedings of FOCS 2003, pp. 606–617 (2003)
Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: Proceedings STOC 2003, pp. 365–372 (2003)
Hajiaghayi, M.T., Jain, K.: The Prize-Collecting Generalized Steiner Tree Problem via a new approach of Primal-Dual Schema. In: Proceedings of SODA 2006, pp. 631–640 (2006)
Hassin, R.: Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research 17(1), 36–42 (1992)
Hassin, R., Levin, A.: Minimum Restricted Diameter Spanning trees. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 175–184. Springer, Heidelberg (2002)
Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9, 256–278 (1974)
Kumar, A., Gupta, A., Roughgarden, T.: A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. In: Proceedings of FOCS 2002, pp. 333–342 (2002)
Marathe, M., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D., Hunt, H.: Bicriteria network design problems. J. Algorithms 28(1), 141–171 (1998)
Meyerson, A., Munagala, K., Plotkin, S.: Cost-Distance: Two Metric Network Design. In: Proceedings of FOCS 2000, pp. 383–388 (2000)
Moss, A., Rabani, Y.: Approximation algorithms for constrained node weighted steiner tree problems. In: Proceedings of STOC 2001, pp. 373–382 (2001)
Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.: Spanning trees short or small. SIAM Journal on Discrete Mathematics 9(2), 178–200 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hajiaghayi, M.T., Kortsarz, G., Salavatipour, M.R. (2006). Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2006 2006. Lecture Notes in Computer Science, vol 4110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11830924_16
Download citation
DOI: https://doi.org/10.1007/11830924_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38044-3
Online ISBN: 978-3-540-38045-0
eBook Packages: Computer ScienceComputer Science (R0)