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)

Full work available at URL: https://doi.org/10.1137/s0895480197329776

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, Unnamed Item, Unnamed Item, The capacitated single-source p-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique, The Euclidean k-Supplier Problem, Constant factor approximation algorithm for uniform hard capacitated knapsack median problem, Capacitated Covering Problems in Geometric Spaces, Unnamed Item, Unnamed Item, On the cost of essentially fair clusterings, Approximation algorithms for the individually fair \(k\)-center with outliers, Universal Algorithms for Clustering Problems, Dynamically second-preferred \(p\)-center problem, Improved bounds for metric capacitated covering problems, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, Mind the gap: edge facility location problems in theory and practice, 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, A scalable exact algorithm for the vertex \(p\)-center problem, \(k\)-balanced center location problem: a new multi-objective facility location problem, Improved approximation algorithms for capacitated fault-tolerant \(k\)-center, \(k\)-center problems with minimum coverage, A constant-factor approximation algorithm for the \(k\)-median problem, Faster balanced clusterings in high dimension, Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints, Approximation algorithms for clustering with dynamic points, LP-based approximation for uniform capacitated facility location problem, Capacitated covering problems in geometric spaces, 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, Client assignment problems for latency minimization, Improved PTAS for the constrained \(k\)-means 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, Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier, The load-distance balancing problem