{"id":{"repo_id":"manitoba","oai_identifier":"oai:mspace.lib.umanitoba.ca:1993/39608"},"canonical_url":"https://search.dev.ndltd.org/etd/manitoba/oai:mspace.lib.umanitoba.ca:1993/39608","repository":{"repo_id":"manitoba","name":"University of Manitoba","base_url":"https://mspace.lib.umanitoba.ca/oai/request"},"display":{"title":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Rahimzad Lamey, Sahar"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Durocher, Stephane","Li, Pak Ching"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-12-16","date_published":"2025-12-16","updated_at":"2026-08-21T22:21:56Z","subjects":["Approximation Algorithms","Approximation Factor","Fault Tolerant K-Centers","Np-hard","Reduction","3-SAT"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1993/39608","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"source_record":{"url":"https://mspace.lib.umanitoba.ca/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amspace.lib.umanitoba.ca%3A1993%2F39608","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.supervisor","label":"Supervisor","values":["Durocher, Stephane","Li, Pak Ching"]},{"key":"dc:creator","label":"Author","values":["Rahimzad Lamey, Sahar"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-01-21T14:23:10Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-01-21T14:23:10Z"]},{"key":"dc:date.issued","label":"Date","values":["2025-12-16"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Approximation Algorithms","Approximation Factor","Fault Tolerant K-Centers","Np-hard","Reduction","3-SAT"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1993/39608"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Fault tolerant Euclidean K-Centers"]}]}],"canonical_facts":{"dc:contributor.supervisor":["Durocher, Stephane","Li, Pak Ching"],"dc:creator":["Rahimzad Lamey, Sahar"],"dc:date.accessioned":["2026-01-21T14:23:10Z"],"dc:date.available":["2026-01-21T14:23:10Z"],"dc:date.issued":["2025-12-16"],"dc:description.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."],"dc:identifier.uri":["http://hdl.handle.net/1993/39608"],"dc:language.iso":["eng"],"dc:subject":["Approximation Algorithms","Approximation Factor","Fault Tolerant K-Centers","Np-hard","Reduction","3-SAT"],"dc:title":["Fault tolerant Euclidean K-Centers"]},"updated_at":"2026-08-21T22:21:56Z"}