Fault tolerant Euclidean K-Centers

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.

Author dc:creator

• Rahimzad Lamey, Sahar

Advisors dc:contributor.supervisor

• Durocher, Stephane
• Li, Pak Ching

• Approximation Algorithms
• Approximation Factor
• Fault Tolerant K-Centers
• Np-hard
• Reduction
• 3-SAT

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1993/39608

OAI record oai:identifier

https://mspace.lib.umanitoba.ca/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amspace.lib.umanitoba.ca%3A1993%2F39608