The Capacitated K-Center Problem

DOI10.1137/S0895480197329776zbMath0947.05073MaRDI QIDQ4490794

Samir Khuller, Yoram J. Sussmann

Publication date: 20 July 2000

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

facility location; approximation algorithms; \(K\)-center

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

68W10: Parallel algorithms in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Large-scale local search heuristics for the capacitated vertexp-center problem, New approximation results for resource replication problems, A simple greedy approximation algorithm for the minimum connected \(k\)-center problem, Capacitated \(p\)-center problem with failure foresight, When centers can fail: a close second opportunity, Graph clustering, The fault-tolerant capacitated \(K\)-center problem, A model for minimizing active processor time, Centrality of trees for capacitated \(k\)-center, Lagrangean duals and exact solution to the capacitated \(p\)-center problem, \(k\)-center problems with minimum coverage, A constant-factor approximation algorithm for the \(k\)-median problem, A PTAS for the cardinality constrained covering with unit balls, A simple linear algorithm for computing rectilinear 3-centers, An exact algorithm for the capacitated vertex \(p\)-center problem, The load-distance balancing problem