On Uniform Capacitated k-Median Beyond the Natural LP Relaxation

DOI10.1137/1.9781611973730.47zbMath1371.90077arXiv1409.6739OpenAlexW2951295184MaRDI QIDQ5362988

Shi Li

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.6739

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (19)

An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ Capacitated covering problems in geometric spaces ⋮ Improved bounds for metric capacitated covering problems ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem ⋮ An approximation algorithm for soft capacitated \(k\)-facility location problem ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ Robust \(k\)-center with two types of radii ⋮ Constant-Factor FPT Approximation for Capacitated k-Median ⋮ Robust \(k\)-center with two types of radii ⋮ Generalized Center Problems with Outliers ⋮ Constant factor approximation algorithm for uniform hard capacitated knapsack median problem ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ To close is easier than to open: dual parameterization to \(k\)-median

This page was built for publication: On Uniform Capacitated k-Median Beyond the Natural LP Relaxation