Abstract
We consider a generalization of the connected facility location problem where the clients must be connected to the open facilities via shared capacitated (tree) networks instead of independent shortest paths. This problem arises in the planning of fiber optic telecommunication access networks, for example. Given a set of clients with positive demands, a set of potential facilities with opening costs, a set of capacitated access cable types, and a core cable type of infinite capacity, one has to decide which facilities to open, how to interconnect them using a Steiner tree of infinite capacity core cables, and which access cable types to install on which potential edges such that these edges form a forest and the installed capacities suffice to simultaneously route the client demands to the open facilities via single paths. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for problem instances where the access cable types obey economies of scale. In the special case where only multiples of a single cable type can be installed on the access edges, a variant of our algorithm achieves a performance guarantee of 6.72.
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
Ahmadian, S., Swamy, C.: Improved Approximation Guarantees for Lower-Bounded Facility Location. In: Proc. of WAOA (2012)
Byrka, J.: An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX and RANDOM 2007. LNCS, vol. 4627, pp. 29–43. Springer, Heidelberg (2007)
Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: An improved LP-based approximation for Steiner tree. In: Proc. of STOC 2010, pp. 583–592 (2010)
Eisenbrand, F., Grandoni, F., Rothvoß, T., Schäfer, G.: Connected facility location via random facility sampling and core detouring. Journal of Computer and System Sciences 76, 709–726 (2010)
Garg, N., Khandekar, R., Konjevod, G., Ravi, R., Salman, F.S., Sinha, A.: On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 170–184. Springer, Heidelberg (2001)
Grandoni, F., Rothvoß, T.: Network design via core detouring for problems without a core. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 490–502. Springer, Heidelberg (2010)
Grandoni, F., Rothvoß, T.: Approximation algorithms for single and multi-commodity connected facility location. In: Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 248–260. Springer, Heidelberg (2011)
Guha, S., Meyerson, A., Munagala, K.: Hierarchical placement and network design problems. In: Proc. of FOCS 2000, pp. 603–612 (2000)
Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problems. In: Proc. of STOC 2001, pp. 383–388 (2001)
Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: A network design problem for multicommodity flow. In: Proc. of STOC 2001, pp. 389–398 (2001)
Hassin, R., Ravi, R., Salman, F.S.: Approximation algorithms for a capacitated network design problem. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 167–176. Springer, Heidelberg (2000)
Jothi, R., Raghavachari, B.: Improved approximation algorithms for the single-sink buy-at-bulk network design problems. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 336–348. Springer, Heidelberg (2004)
Ravi, R., Sinha, A.: Integrated logistics: Approximation algorithms combining facility location and network design. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 212–229. Springer, Heidelberg (2002)
Svitkina, Z.: Lower-bounded facility location. Trans. on Algorithms 6(4) (2010)
Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40, 245–269 (2004)
Talwar, K.: The single-sink buy-at-bulk LP has constant integrality gap. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 475–480. Springer, Heidelberg (2002)
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
Bley, A., Hashemi, S.M., Rezapour, M. (2013). Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem. In: Chan, TH.H., Lau, L.C., Trevisan, L. (eds) Theory and Applications of Models of Computation. TAMC 2013. Lecture Notes in Computer Science, vol 7876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38236-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-38236-9_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38235-2
Online ISBN: 978-3-642-38236-9
eBook Packages: Computer ScienceComputer Science (R0)