The heterogeneous capacitated k-center problem

DOI10.1007/978-3-319-59250-3_11zbMATH Open1418.90271arXiv1611.07414OpenAlexW2556333573MaRDI QIDQ2401151FDOQ2401151

Authors: Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Amit Kumar 

Publication date: 31 August 2017

Abstract: In this paper we initiate the study of the heterogeneous capacitated $k$-center problem: given a metric space $X=(FcupC,d)$, and a collection of capacities. The goal is to open each capacity at a unique facility location in $F$, and also to assign clients to facilities so that the number of clients assigned to any facility is at most the capacity installed; the objective is then to minimize the maximum distance between a client and its assigned facility. If all the capacities $c_i$'s are identical, the problem becomes the well-studied uniform capacitated $k$-center problem for which constant-factor approximations are known. The additional choice of determining which capacity should be installed in which location makes our problem considerably different from this problem, as well the non-uniform generalizations studied thus far in literature. In fact, one of our contributions is in relating the heterogeneous problem to special-cases of the classical Santa Claus problem. Using this connection, and by designing new algorithms for these special cases, we get the following results: (a)A quasi-polynomial time $O(logn/epsilon)$-approximation where every capacity is violated by $1+varepsilon$, (b) A polynomial time $O(1)$-approximation where every capacity is violated by an $O(logn)$ factor. We get improved results for the {em soft-capacities} version where we can place multiple facilities in the same location.

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

Recommendations

• The Capacitated K-Center Problem
• The capacitated \(K\)-center problem (extended abstract)
• Centrality of trees for capacitated \(k\)-center
• Constant Factor Approximation for Capacitated k-Center with Outliers
• Capacitated \(k\)-center problem with vertex weights

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Cited In (3)

• Generalized center problems with outliers
• Capacitated center problems with two-sided bounds and outliers
• Generalized center problems with outliers

This page was built for publication: The heterogeneous capacitated \(k\)-center problem

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