Abstract
We consider the minimum cost edge installation problem (MCEI) in a graph G = (V,E) with edge weight w(e) ≥ 0, e ∈ E. We are given a vertex s ∈ V designated as a sink, an edge capacity λ> 0, and a source set S ⊆ V with demand q(v) ∈ [0,λ], v ∈ S. For any edge e ∈ E, we are allowed to install an integer number h(e) of copies of e. The MCEI asks to send demand q(v) from each source v ∈ S along a single path P v to the sink s. A set of such paths can pass through a single copy of an edge in G as long as the total demand along the paths does not exceed the edge capacity λ. The objective is to find a set \({\mathcal P}=\{P_v\mid v\in S\}\) of paths of G that minimizes the installing cost ∑ e ∈ E h(e) w(e). In this paper, we propose a \((15/8+\rho_{\mbox{\tiny{\sc ST}}})\)-approximation algorithm to the MCEI, where \(\rho_{\mbox{\tiny{\sc ST}}}\) is any approximation ratio achievable for the Steiner tree problem.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: EEE Symposium on Foundations of Computer Science (FOCS), pp. 542–547 (1997)
Grandoni, F., Italiano, G.F.: Improved approximation for single-sink buy-at-bulk. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 111–120. Springer, Heidelberg (2006)
Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problem. In: ACM symposium on the Theory of Computing (STOC), pp. 383–388 (2001)
Hassin, R., Ravi, R., Salman, F.S.: Approximation algorithms for a capacitated network design problem. Algorithmica 38, 417–431 (2004)
Khuller, S., Raghavachari, B., Young, N.N.: Balancing minimum spanning and shortest path trees. Algorithmica 14, 305–322 (1993)
Mansour, Y., Peleg, D.: An approximation algorithm for minimum-cost network design. Tech. Report Cs94-22, The Weizman Institute of Science, Rehovot (1994); also presented at the DIMACS Workshop on Robust Communication Network (1998)
Robins, G., Zelikovsky, A.Z.: Improved Steiner tree approximation in graphs. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 770–779 (2000)
Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Approximating the single-sink link-installation problem in network design. SIAM J. Optim. 11, 595–610 (2000)
Zheng, H.-Z., Chu, D.-H., Zhan, D.-C.: Effective algorithm CFL based on Steiner tree and UFL problem. IJCSNS 6(9A), 24–27 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Morsy, E., Nagamochi, H. (2007). Approximation to the Minimum Cost Edge Installation Problem. In: Tokuyama, T. (eds) Algorithms and Computation. ISAAC 2007. Lecture Notes in Computer Science, vol 4835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77120-3_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-77120-3_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77118-0
Online ISBN: 978-3-540-77120-3
eBook Packages: Computer ScienceComputer Science (R0)