Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems

DOI10.1137/1.9781611973730.49zbMath1371.90072arXiv1312.6550OpenAlexW2952695108MaRDI QIDQ5362990

Krzysztof Fleszar, Bartosz Rybicki, Jaroslaw Byrka, Joachim Spoerhase

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/1312.6550

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (22)

Parameterized complexity of categorical clustering with size constraints ⋮ Approximation algorithm for min-max correlation clustering problem with outliers ⋮ An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation ⋮ Approximation algorithms for two variants of correlation clustering problem ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ Improved bounds for metric capacitated covering problems ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Unnamed Item ⋮ Capacitated facility location with outliers/penalties ⋮ A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem ⋮ An approximation algorithm for soft capacitated \(k\)-facility location problem ⋮ Respecting lower bounds in uniform lower and upper bounded facility location problem ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs ⋮ Constant-Factor FPT Approximation for Capacitated k-Median ⋮ Constant factor approximation algorithm for uniform hard capacitated knapsack median problem ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ Lossy kernelization of same-size clustering

This page was built for publication: Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems