Fault tolerant \(K\)-center problems

DOI10.1016/S0304-3975(98)00222-9zbMath0944.68141WikidataQ127771321 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 location; fault-tolerance; approximation algorithms; \(K\)-center

Mathematics Subject Classification ID

90B85: Continuous location

90C59: Approximation methods and heuristics in mathematical programming

68W25: Approximation algorithms

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

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

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