The Capacitated K-Center Problem

DOI10.1137/S0895480197329776MaRDI QIDQ4490794zbMATH OpenOpenAlexFDO

Authors 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

\(K\)-centerapproximation algorithmsfacility location

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• The capacitated K-center problem (extended abstract)
• Fault tolerant \(K\)-center problems
• Approximation algorithms for hard capacitated \(k\)-facility location problems
• Constant Factor Approximation for Capacitated k-Center with Outliers
• Centrality of trees for capacitated \(k\)-center

Cited in

(79)

• Lagrangean duals and exact solution to the capacitated \(p\)-center problem
• Fault tolerant \(K\)-center problems
• 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
• On the k-center problem with many centers
• A constant-factor approximation algorithm for the k-median problem
• Donation center location 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
• Solving \(k\)-center problems involving sets based on optimization techniques
• An adaptive probabilistic algorithm for online \(k\)-center clustering
• The heterogeneous capacitated \(k\)-center problem
• Capacitated center problems with two-sided bounds and outliers
• 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
• New approximation results for resource replication problems
• A simple greedy approximation algorithm for the minimum connected k-center problem
• The load-distance balancing problem
• Donation center location problem
• THE ALIGNED K-CENTER PROBLEM
• Capacitated p-center problem with failure foresight
• When centers can fail: a close second opportunity
• Technical Note—A Polynomial Algorithm for the Equal Capacity p-Center Problem on Trees
• Large-scale local search heuristics for the capacitated vertexp-center problem
• Graph clustering
• The capacitated K-center problem (extended abstract)
• Capacitated k-center problem with vertex weights
• Computing and Combinatorics
• The fault-tolerant capacitated \(K\)-center problem
• The capacitated single-source \(p\)-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique
• Privacy preserving clustering with constraints
• Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
• The Euclidean k-supplier problem
• Capacitated covering problems in geometric spaces
• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• Capacitated metric labeling
• Centrality of trees for capacitated \(k\)-center
• Integer Programming and Combinatorial Optimization
• scientific article; zbMATH DE number 7651148 (Why is no real title available?)
• scientific article; zbMATH DE number 7651201 (Why is no real title available?)
• On the cost of essentially fair clusterings
• The k-centrum multi-facility location problem
• 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
• New algorithms for fair \(k\)-center problem with outliers and capacity constraints
• 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
• The fair \(k\)-center with outliers problem: FPT and polynomial approximations
• Bike rebalancing: how to find a balanced matching in the k center problem?
• The parameterized complexity of terminal monitoring set
• A constructive heuristic for the uniform capacitated vertex \(k\)-center problem
• Variants of Euclidean k-center clusterings
• Connected k-center and k-diameter clustering
• The distributed algorithms for the lower-bounded \(k\)-center clustering in metric space
• Mixed-integer linear programming approaches for nested p-center problems with absolute and relative regret objectives
• A constant-factor approximation for pairwise fair k-center clustering
• A fixed-parameter tractable approximation for capacitated k-supplier
• A fast 3-approximation for the capacitated tree cover problem with edge loads
• Moderate dimension reduction for k-center clustering
• An approximation algorithm for the parity-constrained k-supplier problem
• Universal algorithms for clustering problems
• An improved approximation algorithm for the k-supplier problem with parameterized triangle inequality
• An improved two-stage approximation algorithm for the k-supplier problem with parameterized triangle inequality
• Centrality of trees for capacitated \(k\)-center

This page was built for publication: The Capacitated K-Center Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4490794)