Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Bounds for Metric Capacitated Covering Problems
385
0
0.0
(
0
)
Added by
Sayan Bandyapadhyay
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Sayan Bandyapadhyay
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
In this paper, we study the lower- and upper-bounded covering (LUC) problem, where we are given a set $P$ of $n$ points, a collection $mathcal{B}$ of balls, and parameters $L$ and $U$. The goal is to find a minimum-sized subset $mathcal{B}subseteq mathcal{B}$ and an assignment of the points in $P$ to $mathcal{B}$, such that each point $pin P$ is assigned to a ball that contains $p$ and for each ball $B_iin mathcal{B}$, at least $L$ and at most $U$ points are assigned to $B_i$. We obtain an LP rounding based constant approximation for LUC by violating the lower and upper bound constraints by small constant factors and expanding the balls by again a small constant factor. Similar results were known before for covering problems with only the upper bound constraint. We also show that with only the lower bound constraint, the above result can be obtained without any lower bound violation. Covering problems have close connections with facility location problems. We note that the known constant-approximation for the corresponding lower- and upper-bounded facility location problem, violates the lower and upper bound constraints by a constant factor.
A covering code is a subset $mathcal{C} subseteq {0,1}^n$ with the property that any $z in {0,1}^n$ is close to some $c in mathcal{C}$ in Hamming distance. For every $epsilon,delta>0$, we show a construction of a family of codes with relative covering radius $delta + epsilon$ and rate $1 - mathrm{H}(delta) $ with block length at most $exp(O((1/epsilon) log (1/epsilon)))$ for every $epsilon > 0$. This improves upon a folklore construction which only guaranteed codes of block length $exp(1/epsilon^2)$. The main idea behind this proof is to find a distribution on codes with relatively small support such that most of these codes have good covering properties.
In the metric multi-cover problem (MMC), we are given two point sets $Y$ (servers) and $X$ (clients) in an arbitrary metric space $(X cup Y, d)$, a positive integer $k$ that represents the coverage demand of each client, and a constant $alpha geq 1$. Each server can have a single ball of arbitrary radius centered on it. Each client $x in X$ needs to be covered by at least $k$ such balls centered on servers. The objective function that we wish to minimize is the sum of the $alpha$-th powers of the radii of the balls. In this article, we consider the MMC problem as well as some non-trivial generalizations, such as (a) the non-uniform MMC, where we allow client-specific demands, and (b) the $t$-MMC, where we require the number of open servers to be at most some given integer $t$. For each of these problems, we present an efficient algorithm that reduces the problem to several instances of the corresponding $1$-covering problem, where the coverage demand of each client is $1$. Our reductions preserve optimality up to a multiplicative constant factor. Applying known constant factor approximation algorithms for $1$-covering, we obtain the first constant approximations for the MMC and these generalizations.
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)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
