Abstract
We consider the Fault-Tolerant Facility Placement problem (\(FTFP\)), which is a generalization of the classical Uncapacitated Facility Location problem (\(UFL\)). In the \(FTFP\) problem we have a set of clients \(C\) and a set of facilities \(F\). Each facility \(i \in F\) can be opened many times. For each opening of facility \(i\) we pay \(f_i \ge 0\). Our goal is to connect each client \(j \in C\) with \(r_j \ge 1\) open facilities in a way that minimizes the total cost of open facilities and established connections.
In a series of recent papers \(FTFP\) was essentially reduced to Fault-Tolerant Facility Location problem (\(FTFL\)) and then to \(UFL\) showing it could be approximated with ratio \(1.575\). In this paper we show that \(FTFP\) can actually be approximated even better. We consider approximation ratio as a function of \(r = min_{j \in C}~r_j\) (minimum requirement of a client). With increasing \(r\) the approximation ratio of our algorithm \(\lambda _r\) converges to one. Furthermore, for \(r > 1\) the value of \(\lambda _r\) is less than 1.463 (hardness of approximation of \(UFL\)). We also show a lower bound of 1.278 for the approximability of the \(FTFL\) for arbitrary \(r\). Already for \(r > 3\) we obtain that \(FTFP\) can be approximated with ratio 1.275, showing that under standard complexity theoretic assumptions \(FTFP\) is strictly better approximable than \(FTFL\).
B. Rybicki—Research supported by NCN 2012/07/N/ST6/03068 grant.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
An algorithm for UFL is called (a,b)-approximation if the cost of returned solution is upper bounded by \(a \cdot F^* + b \cdot C^*\), where \(F^*\) and \(C^*\) are, respectively, the costs of establishing connections and opening facilities in an optimal solution.
References
Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45–58 (2013)
Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: STOC, pp. 731–740 (2002)
Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC, pp. 624–633 (2014)
Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 240–257. Springer, Heidelberg (2002)
Byrka, J., Aardal, K.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39(6), 2212–2231 (2010)
Shmoys, D., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems (Extended abstract). In: STOC, pp. 265–274 (1997)
Yan, L.: Approximation algorithms for the Fault-Tolerant facility placement problem, Ph.D. Thesis
Yan, L., Chrobak, M.: Approximation algorithms for the Fault-Tolerant facility placement problem. Inf. Process. Lett. 111(11), 545–549 (2011)
Feige, U.: A threshold of ln n for approximating set-cover. In: 28th ACM Symposium on Theory of Computing, pp. 314–318 (1996)
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324–360 (2006)
Byrka, J., Srinivasan, A., Swamy, C.: Fault-Tolerant facility location: a randomized dependent lp-rounding algorithm. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 244–257. Springer, Heidelberg (2010)
Swamy, C., Shmoys, D.: Fault-Tolerant facility location. ACM Trans. Algorithms 4(4), 1–27 (2008)
Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 228–248. SIAM, Philadelphia (1998)
Guha, S., Meyerson, A., Munagala, K.: Improved algorithms for fault tolerant facility location. In: SODA, pp. 636–641 (2001)
Rybicki, B., Byrka, J.: Improved approximation algorithm for Fault-Tolerant Facility Placement. CoRR abs/1311.6615 (2013)
Chudak, F., Shmoys, D.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1–25 (2003)
Byrka, J., Ghodsi, M., Srinivasan, A.: LP-rounding algorithms for facility-location problems. CoRR abs/1007.3611 (2010)
Yan, L., Chrobak, M.: LP-rounding Algorithms for the Fault-Tolerant Facility Placement Problem. CoRR abs/1205.1281 (2012)
Xu, S., Shen, H.: The Fault-Tolerant facility allocation problem. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 689–698. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Rybicki, B., Byrka, J. (2015). Improved Approximation Algorithm for Fault-Tolerant Facility Placement. In: Bampis, E., Svensson, O. (eds) Approximation and Online Algorithms. WAOA 2014. Lecture Notes in Computer Science(), vol 8952. Springer, Cham. https://doi.org/10.1007/978-3-319-18263-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-18263-6_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18262-9
Online ISBN: 978-3-319-18263-6
eBook Packages: Computer ScienceComputer Science (R0)