Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCapacitated Center Problems with Two-Sided Bounds and Outliers
333
0
0.0
(
0
)
Added by
Lunjia Hu
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In recent years, the capacitated center problems have attracted a lot of research interest. Given a set of vertices $V$, we want to find a subset of vertices $S$, called centers, such that the maximum cluster radius is minimized. Moreover, each center in $S$ should satisfy some capacity constraint, which could be an upper or lower bound on the number of vertices it can serve. Capacitated $k$-center problems with one-sided bounds (upper or lower) have been well studied in previous work, and a constant factor approximation was obtained. We are the first to study the capacitated center problem with both capacity lower and upper bounds (with or without outliers). We assume each vertex has a uniform lower bound and a non-uniform upper bound. For the case of opening exactly $k$ centers, we note that a generalization of a recent LP approach can achieve constant factor approximation algorithms for our problems. Our main contribution is a simple combinatorial algorithm for the case where there is no cardinality constraint on the number of open centers. Our combinatorial algorithm is simpler and achieves better constant approximation factor compared to the LP approach.
rate research
Read More
We study the $mathcal{F}$-center problem with outliers: given a metric space $(X,d)$, a general down-closed family $mathcal{F}$ of subsets of $X$, and a parameter $m$, we need to locate a subset $Sin mathcal{F}$ of centers such that the maximum distance among the closest $m$ points in $X$ to $S$ is minimized. Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient $3$-approximation for the $mathcal{F}$-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over $mathcal{F}$ subject to a partition constraint. One concrete upshot of our result is a polynomial time $3$-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.
In the Metric Capacitated Covering (MCC) problem, given a set of balls $mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$, the goal is to find a minimum sized subset $mathcal{B}subseteq mathcal{B}$ and an assignment of the points in $P$ to the balls in $mathcal{B}$ such that each point is assigned to a ball that contains it and each ball is assigned with at most $U$ points. MCC achieves an $O(log |P|)$-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of $o(log |P|)$ even with $beta < 3$ factor expansion of the balls. Bandyapadhyay~{et al.} [SoCG 2018, DCG 2019] showed that one can obtain an $O(1)$-approximation for the problem with $6.47$ factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound $3$ and the upper bound $6.47$. In this current work, we show that it is possible to obtain an $O(1)$-approximation with only $4.24$ factor expansion of the balls. We also show a similar upper bound of $5$ for a more generalized version of MCC for which the best previously known bound was $9$.
In this paper we initiate the study of the heterogeneous capacitated $k$-center problem: given a metric space $X = (F cup C, 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(log n/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(log n)$ factor. We get improved results for the {em soft-capacities} version where we can place multiple facilities in the same location.
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/varepsilon^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)$.
We discuss folklore statements about distance functions in manifolds with two sided bounded curvature. The topics include regularity, subsets of positive reach and the cut locus.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
