An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation

DOI10.1007/978-3-319-33461-5_22zbMath1419.90091arXiv1511.07494OpenAlexW2262337340MaRDI QIDQ3186508

Sumedha Uniyal, Bartosz Rybicki, Jaroslaw Byrka

Publication date: 10 August 2016

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (20)

Parameterized complexity of categorical clustering with size constraints ⋮ An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ An approximation algorithm for the dynamic facility location problem with outliers ⋮ 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 ⋮ Unnamed Item ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ Parameterized complexity of categorical clustering with size constraints ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ 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 ⋮ To close is easier than to open: dual parameterization to \(k\)-median

Cites Work

• Unnamed Item
• Approximation algorithms for hard capacitated \(k\)-facility location problems
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• LP-Based Algorithms for Capacitated Facility Location
• An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
• Dependent rounding and its applications to approximation algorithms
• Approximating capacitated k-median with (1 + ∊)k open facilities
• Local Search Heuristics for k-Median and Facility Location Problems
• On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Approximating k-median via pseudo-approximation

This page was built for publication: An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation