The Capacitated K-Center Problem
From MaRDI portal
Publication:4490794
DOI10.1137/S0895480197329776zbMath0947.05073OpenAlexW2055996587MaRDI 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
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (47)
New approximation results for resource replication problems ⋮ A simple greedy approximation algorithm for the minimum connected \(k\)-center problem ⋮ The load-distance balancing problem ⋮ A scalable exact algorithm for the vertex \(p\)-center problem ⋮ Capacitated \(p\)-center problem with failure foresight ⋮ When centers can fail: a close second opportunity ⋮ Approximation algorithms for clustering with dynamic points ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ Approximation algorithms for the individually fair \(k\)-center with outliers ⋮ Capacitated covering problems in geometric spaces ⋮ Universal Algorithms for Clustering Problems ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Centrality of trees for capacitated \(k\)-center ⋮ 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 ⋮ The Euclidean k-Supplier Problem ⋮ Client assignment problems for latency minimization ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Mind the gap: edge facility location problems in theory and practice ⋮ Massively parallel and streaming algorithms for balanced clustering ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Graph clustering ⋮ \(k\)-balanced center location problem: a new multi-objective facility location problem ⋮ The fault-tolerant capacitated \(K\)-center problem ⋮ A model for minimizing active processor time ⋮ On the cost of essentially fair clusterings ⋮ Improved approximation algorithms for capacitated fault-tolerant \(k\)-center ⋮ Faster balanced clusterings in high dimension ⋮ A simple linear algorithm for computing rectilinear 3-centers ⋮ \(k\)-center problems with minimum coverage ⋮ An exact algorithm for the capacitated vertex \(p\)-center problem ⋮ A unified framework for clustering constrained data without locality property ⋮ Constant factor approximation algorithm for uniform hard capacitated knapsack median problem ⋮ An adaptive probabilistic algorithm for online \(k\)-center clustering ⋮ Unnamed Item ⋮ The capacitated single-source p-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique ⋮ Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints ⋮ Large-scale local search heuristics for the capacitated vertexp-center problem ⋮ Lagrangean duals and exact solution to the capacitated \(p\)-center problem ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ A constant-factor approximation algorithm for the \(k\)-median problem
This page was built for publication: The Capacitated K-Center Problem
