Fault-Tolerant Covering Problems in Metric Spaces
- PDF / 570,638 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 213 Views
Fault-Tolerant Covering Problems in Metric Spaces Santanu Bhowmick1 · Tanmay Inamdar1
· Kasturi Varadarajan1
Received: 17 October 2018 / Accepted: 24 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 ∪ Y , d), a positive integer k that represents the coverage demand of each client, and a constant α ≥ 1. Each server can host a single ball of arbitrary radius centered on it. Each client x ∈ 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 α-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. Keywords Approximation algorithms · Multi-covering · Fault-tolerant covering · Metric spaces
This material is based upon work supported by the National Science Foundation under Grants CCF-1318996 and CCF-1615845.
B
Tanmay Inamdar [email protected] Santanu Bhowmick [email protected] Kasturi Varadarajan [email protected]
1
Department of Computer Science, Iowa City, IA, USA
123
Algorithmica
1 Introduction In the metric multi-cover problem (MMC), the input consists of two point sets Y (servers) and X (clients) in an arbitrary metric space (X ∪ Y , d), a positive integer k that represents the coverage demand of each client, and a constant α ≥ 1. Consider an assignment r : Y → R+ of radii to each server in Y . This can be viewed as specifying a ball of radius r (y) at each server y ∈ Y . If, for each client x ∈ X , at least j of the corresponding server balls contain x, then we say that X is j-covered by r . That is, X is j-covered if for each x ∈ X , |{y ∈ Y | d(x, y) ≤ r (y)}| ≥ j. The cost of assignment r is defined to be the sum of the α-th powers of radii of the corresponding balls. That is, cost(r ) = y∈Y (r (y))α . Any assignment r : Y → R+ that k-covers X is afeasible solution to the MMC problem. The objective to be minimized is the cost y∈Y (r (y))α . We assume that k ≤ |Y |, for otherwise there is no feasible solution. In this article, we consider the MMC as well as some more general variants. In one vari
Data Loading...
