Abstract
The paper concerns a new variant of the hierarchical facility location problem on metric powers (\({{\rm \sc HFL}_\beta[h]}\)), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D 1,D 2,...,D h − 1 of locations that may open an intermediate transmission station and a set D h of locations of clients. Each client in D h must be serviced by an open transmission station in D h − 1 and every open transmission station in D l must be serviced by an open transmission station on the next lower level, D l − 1. An open transmission station on the first level, D 1 must be serviced by an open facility. The cost of assigning a station j on level l ≥ 1 to a station i on level l-1 is c ij . For i∈ F, the cost of opening a facility at location i is f i ≥ 0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth steiner tree and the bounded hop strong-connectivity range assignment problems.
Supported in part by a grant from the Israel Ministry of Science and Technology.
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
Althaus, E., Funke, S., Har-Peled, S., Koenemann, J., Ramos, E.A., Skutella, M.: Approximation k-hop minimum-spanning trees. Operations Research Letters 33, 115–120 (2005)
Bar-ilan, J., Kortsarz, G., Peleg, D.: Generalized aubmodular cover problems and applications. In: Proc. 4th Israel Symp. on Theory of Computing and Systems, pp. 110–118 (1996)
Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. In: Proc. 9th ACM-SIAM Symp. on Discrete Algorithms, pp. 192–200 (1998)
Chudak, F.A.: Improved approximation algorithm for uncapacitated facility location problem. In: Proc. 6th Conf. on Integer Programing and Combinatorial Optimization, pp. 180–194 (1998)
Clementi, A.E.F., Penna, P., Ferreira, A., Perennes, S., Silvestri, R.: The minimum range assignment problem on linear radio networks. Algorithmica 35(2), 95–110 (2003)
Clementi, A.E.F., Penna, P., Silvestri, R.: On the power assignment problem in radio networks. Mobile Network Applic. 9(2), 125–140 (2004)
Feige, U.: A threshold of ln n for approximating set cover. In: Proc. 28th ACM Symp. on Theory of Computing, pp. 314–318 (1996)
Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company, New York (1979)
Aardal, K., Chudak, A.F., Shmoys, B.D.: A 3-approximation algorithm for the K-level uncapacitated facility location problem. Information Processing Letters 72, 161–167 (1999)
Kirousis, L.M., Kranakis, E., Kriznac, D., Pelc, A.: Power consumption in packet radio networks. In: Proc. 14th Symp. on Theoretical Aspects of Computer Science, pp. 363–374 (1997)
Kortsarz, G., Peleg, D.: Approximating the weight of shallow steiner trees. Discrete Applied Math., 265–285 (1999)
Lin, J.H., Vitter, J.S.: ε−approximations with small packing constraint violation. In: Proc. 24th ACM Symp. on Theory of Computing, pp. 771–782 (1992)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41, 960–981 (1994)
Mahdian, M., Ye, Y., Zhang, J.: A 1.52-approximation algorithm for the uncapacitated facility location problem. In: Proc. 5th Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 229–242 (2002)
Shmoys, B.D., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems. In: Proc. 29th ACM Symp. on Theory of Computing, pp. 265–274 (1997)
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
Kantor, E., Peleg, D. (2006). Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_22
Download citation
DOI: https://doi.org/10.1007/11758471_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34375-2
Online ISBN: 978-3-540-34378-3
eBook Packages: Computer ScienceComputer Science (R0)