Bi-factor approximation algorithms for hard capacitated k-median problems

DOI10.1137/1.9781611973730.49MaRDI QIDQ5362990zbMATH OpenOpenAlexFDO

Authors Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, 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) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Abstract: The $k$-Facility Location problem is a generalization of the classical problems $k$-Median and Facility Location. The goal is to select a subset of at most $k$ facilities that minimizes the total cost of opened facilities and established connections between clients and opened facilities. We consider the hard-capacitated version of the problem, where a single facility may only serve a limited number of clients and creating multiple copies of a facility is not allowed. We construct approximation algorithms slightly violating the capacities based on rounding a fractional solution to the standard LP. It is well known that the standard LP (even in the case of uniform capacities and opening costs) has unbounded integrality gap if we only allow violating capacities by a factor smaller than $2$, or if we only allow violating the number of facilities by a factor smaller than $2$. In this paper, we present the first constant-factor approximation algorithms for the hard-capacitated variants of the problem. For uniform capacities, we obtain a $(2+varepsilon)$-capacity violating algorithm with approximation ratio $O(1/varepsilo{n}^2)$; our result has not yet been improved. Then, for non-uniform capacities, we consider the case of $k$-Median, which is equivalent to $k$-Facility Location with uniform opening cost of the facilities. Here, we obtain a $(3+varepsilon)$-capacity violating algorithm with approximation ratio $O(1/varepsilon)$.

Recommendations

• An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• On uniform capacitated k-median beyond the natural LP relaxation
• Approximating k-median with non-uniform capacities
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation

Cited in

(34)

• A local search approximation algorithm for the uniform capacitated k-facility location problem
• An approximation algorithm for soft capacitated k-facility location problem
• Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs
• An approximation algorithm for the uniform capacitated \(k\)-means problem
• Lossy kernelization of same-size clustering
• Approximation algorithm for min-max correlation clustering problem with outliers
• Approximation algorithms for two variants of correlation clustering problem
• LP-based approximation for uniform capacitated facility location problem
• Respecting lower bounds in uniform lower and upper bounded facility location problem
• Approximating k-median with non-uniform capacities
• An improved approximation algorithm for the hard uniform capacitated k-median problem
• An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
• Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
• Recent developments in approximation algorithms for facility location and clustering problems
• On uniform capacitated k-median beyond the natural LP relaxation
• Constant-Factor FPT Approximation for Capacitated k-Median
• Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
• On the fixed-parameter tractability of capacitated clustering
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• scientific article; zbMATH DE number 7651148 (Why is no real title available?)
• A unified framework of FPT approximation algorithms for clustering problems
• Parameterized complexity of categorical clustering with size constraints
• Improved bounds for metric capacitated covering problems
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• Capacitated facility location with outliers/penalties
• Lossy kernelization of same-size clustering
• FPT approximation for capacitated clustering with outliers
• Respecting lower bounds in uniform lower and upper bounded facility location problem
• A polynomial-time exact algorithm for the connected k-facility location problem on trees
• Approximation algorithm for min-max correlation clustering problem with penalties
• Uniform capacitated facility location with outliers/penalties
• Approximation scheme for the single-client capacitated facility location problem with operational cost budget constraint
• Parameterized complexity of categorical clustering with size constraints

This page was built for publication: Bi-factor approximation algorithms for hard capacitated \(k\)-median problems

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