Fault tolerant Euclidean K-Centers

Abstract

The Euclidean k -center problem is a fundamental question in computational geometry and facility location. Given a set P of n points in Rd, the goal is to choose a set F of k center points such that the maximum distance from any point in P to its nearest center in F is minimized. Geometrically, this corresponds to covering all points in P with k balls of minimal radius. We study a natural generalization known as the ℓ-fault-tolerant Euclidean k - center problem, which introduces a robustness parameter ℓ ≤ k. In this variant, each point in P must be covered by at least ℓ of the k balls, or equivalently, its distance to the ℓth nearest center in F must be minimized. This captures scenarios where redundancy is required for fault tolerance or load balancing. Our contributions include an exact O(n log n)-time algorithm for solving the problem in one dimension (R), where a linear order among points can be exploited. In two dimensions (R2), we prove that the problem becomes NP-hard. Nevertheless, we present an O(nk/ℓ)-time algorithm that computes a 2-approximation, offering an efficient and practical solution with provable guarantees.