Abstract
In this article, we study some fault-tolerant covering problems in metric spaces. In the metric multi-cover problem (MMC), we are given two point sets Y (servers) and X (clients) in an arbitrary metric space \((X \cup Y, d)\), a positive integer k that represents the coverage demand of each client, and a constant \(\alpha \ge 1\). Each server can host a single ball of arbitrary radius centered on it. Each client \(x \in X\) needs to be covered by at least k such balls centered on servers. The objective function that we wish to minimize is the sum of the \(\alpha \)-th powers of the radii of the balls. We also study some non-trivial generalizations of the MMC, such as (a) the non-uniform MMC, where we allow client-specific demands, and (b) the t-MMC, where we require the number of open servers to be at most some given integer t. We present the first constant approximations for these fault-tolerant covering problems. Our algorithms are based on the following paradigm: for each of the three problems, we present an efficient algorithm that reduces the problem to several instances of the corresponding 1-covering problem, where the coverage demand of each client is 1. The reductions preserve optimality up to a multiplicative constant factor. Applying known constant factor approximation algorithms for 1-covering, we obtain our results for the MMC and these generalizations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The superscripts f and p, in \(Y_i^f\) and \(Y_i^p\), stand for farthest and private, respectively. The reasoning behind these adjectives will be clear once the algorithm for computing these sets is described.
With a more detailed argument, the factor \(12^{\alpha }\) can be improved. For instance, a bound of \(11^{\alpha }\) is almost immediate from the proof.
Let OPT(k, t) be the minimum of \(\sum _{i = 1}^k \texttt {cost}(S(V_i, t_i))\) over all valid k-tuples \((t_1, t_2, \ldots , t_k)\). Then, OPT(k, t) satisfies the following recurrence, which can be used for dynamic programming:
$$ OPT(k, t) = \min _{1 \le t_{k} < t} \Big \{\texttt {cost}(S(V_{k}, t_{k})) + OPT(k-1, t-t_{k}) \Big \}. $$
References
Abu-Affash, A.K., Carmi, P., Katz, M.J., Morgenstern, G.: Multi cover of a polygon minimizing the sum of areas. Int. J. Comput. Geom. Appl. 21(6), 685–698 (2011)
Alt, H., Arkin, E.M., Brönnimann, H., Erickson, J., Fekete, S.P., Knauer, C., Lenchner, J., Mitchell, J.S.B., Whittlesey, K.: Minimum-cost coverage of point sets by disks. In: Symposium on Computational Geometry, pp. 449–458 (2006)
Bandyapadhyay, S., Varadarajan, K.R.: Approximate clustering via metric partitioning. In: Hong, S.-H. (ed.) ISAAC. LIPIcs, vol. 64, pp. 15:1–15:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). ISBN 978-3-95977-026-2
Bar-Yehuda, R., Rawitz, D.: A note on multicovering with disks. Comput. Geom. 46(3), 394–399 (2013)
Bhowmick, S., Varadarajan, K.R., Xue, S.-K.: A constant-factor approximation for multi-covering with disks. In: Symposium on Computational Geometry, pp. 243–248 (2013)
Bhowmick, S., Varadarajan, K.R., Xue, S.-K.: A constant-factor approximation for multi-covering with disks. JoCG 6(1), 220–234 (2015)
Bilò, V., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Geometric clustering to minimize the sum of cluster sizes. In: ESA, pp. 460–471 (2005)
Byrka, J., Aravind, S., Swamy, C.: Fault-tolerant facility location: a randomized dependent lp-rounding algorithm. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 244–257. Springer (2010)
Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2), 417–441 (2004)
Chaudhuri, S., Garg, N., Ravi, R.: The p-neighbor k-center problem. Inf. Process. Lett. 65(3), 131–134 (1998)
Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. In: WAOA, pp. 137–150 (2003)
Gibson, M., Kanade, G., Krohn, E., Pirwani, I.A., Varadarajan, K.: On clustering to minimize the sum of radii. SIAM J. Comput. 41(1), 47–60 (2012)
Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation algorithm for the fault-tolerant facility location problem. J. Algorithms 48(2), 429–440 (2003)
Hajiaghayi, M., Wei, H., Li, J., Li, S., Saha, B.: A constant factor approximation algorithm for fault-tolerant k-median. ACM Trans. Algorithms (TALG) 12(3), 36 (2016)
Khuller, S., Pless, R., Sussmann, Y.J.: Fault tolerant k-center problems. Theor. Comput. Sci. 242(1), 237–245 (2000)
Krumke, S.O.: On a generalization of the p-center problem. Inf. Process. Lett. 56(2), 67–71 (1995)
Kumar, N., Raichel, B.: In: Proceedings of the 25th Canadian Conference on Computational Geometry, CCCG 2013, Waterloo, Ontario, Canada, August 8–10 (2013)
Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Netw. 47(4), 489–501 (2005)
Swamy, C., Shmoys, D.B.: Fault-tolerant facility location. ACM Trans. Algorithms (TALG) 4(4), 51 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This material is based upon work supported by the National Science Foundation under Grants CCF-1318996 and CCF-1615845.
Rights and permissions
About this article
Cite this article
Bhowmick, S., Inamdar, T. & Varadarajan, K. Fault-Tolerant Covering Problems in Metric Spaces. Algorithmica 83, 413–446 (2021). https://doi.org/10.1007/s00453-020-00762-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-020-00762-y