Fault tolerant \(K\)-center problems

DOI10.1016/S0304-3975(98)00222-9zbMath0944.68141OpenAlexW2030016043WikidataQ127771321 ScholiaQ127771321MaRDI QIDQ1575549

Samir Khuller, Robert Pless, Yoram J. Sussmann

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00222-9

zbMATH Keywords

facility locationfault-toleranceapproximation algorithms\(K\)-center

Mathematics Subject Classification ID

Continuous location (90B85) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (30)

A simple greedy approximation algorithm for the minimum connected \(k\)-center problem ⋮ The \(p\)-neighbor \(k\)-center problem ⋮ Matroid and knapsack center problems ⋮ Approximation algorithms for clustering with dynamic points ⋮ Fault-tolerant covering problems in metric spaces ⋮ Hotelling games in fault-prone settings ⋮ GRASP with strategic oscillation for the \(\alpha \)-neighbor \(p\)-center problem ⋮ Approximation algorithms for the individually fair \(k\)-center with outliers ⋮ Clustering with faulty centers ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ New algorithms for fair \(k\)-center problem with outliers and capacity constraints ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exact solution approaches for the discrete α‐neighbor p‐center problem ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem ⋮ The fault-tolerant capacitated \(K\)-center problem ⋮ Improved approximation algorithms for capacitated fault-tolerant \(k\)-center ⋮ Robust fault tolerant uncapacitated facility location ⋮ \(k\)-center problems with minimum coverage ⋮ Asymmetry in \(k\)-center variants ⋮ Mixed fault tolerance in server assignment: combining reinforcement and backup ⋮ A unified framework for clustering constrained data without locality property ⋮ An adaptive probabilistic algorithm for online \(k\)-center clustering ⋮ Unnamed Item ⋮ Fault tolerant \(K\)-center problems ⋮ One-way and round-trip center location problems ⋮ Exploiting flat subspaces in local search for \(p\)-center problem and two fault-tolerant variants

Cites Work

• The \(p\)-neighbor \(k\)-center problem
• A simple heuristic for the p-centre problem
• Clustering to minimize the maximum intercluster distance
• A heuristic for the p-center problem in graphs
• Easy and hard bottleneck location problems
• Fault tolerant \(K\)-center problems
• A Best Possible Heuristic for the k-Center Problem
• `` Strong NP-Completeness Results
• How to Allocate Network Centers
• The capacitated K-center problem
• Bottleneck extrema

This page was built for publication: Fault tolerant \(K\)-center problems