Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Metric Multi-Covering Problems
182
0
0.0
(
0
)
Added by
Santanu Bhowmick
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
We consider variants of the following multi-covering problem with disks. We are given two point sets $Y$ (servers) and $X$ (clients) in the plane, a coverage function $kappa :X rightarrow mathcal{N}$, and a constant $alpha geq 1$. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $x in X$ be covered by at least $kappa(x)$ of the server disks. The objective function we wish to minimize is the sum of the $alpha$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.
In the MINIMUM CONVEX COVER (MCC) problem, we are given a simple polygon $mathcal P$ and an integer $k$, and the question is if there exist $k$ convex polygons whose union is $mathcal P$. It is known that MCC is $mathsf{NP}$-hard [Culberson & Reckhow: Covering polygons is hard, FOCS 1988/Journal of Algorithms 1994] and in $existsmathbb{R}$ [ORourke: The complexity of computing minimum convex covers for polygons, Allerton 1982]. We prove that MCC is $existsmathbb{R}$-hard, and the problem is thus $existsmathbb{R}$-complete. In other words, the problem is equivalent to deciding whether a system of polynomial equations and inequalities with integer coefficients has a real solution. If a cover for our constructed polygon exists, then so does a cover consisting entirely of triangles. As a byproduct, we therefore also establish that it is $existsmathbb{R}$-complete to decide whether $k$ triangles cover a given polygon. The issue that it was not known if finding a minimum cover is in $mathsf{NP}$ has repeatedly been raised in the literature, and it was mentioned as a long-standing open question already in 2001 [Eidenbenz & Widmayer: An approximation algorithm for minimum convex cover with logarithmic performance guarantee, ESA 2001/SIAM Journal on Computing 2003]. We prove that assuming the widespread belief that $mathsf{NP} eqexistsmathbb{R}$, the problem is not in $mathsf{NP}$. An implication of the result is that many natural approaches to finding small covers are bound to give suboptimal solutions in some cases, since irrational coordinates of arbitrarily high algebraic degree can be needed for the corners of the pieces in an optimal solution.
We study several problems on geometric packing and covering with movement. Given a family $mathcal{I}$ of $n$ intervals of $kappa$ distinct lengths, and another interval $B$, can we pack the intervals in $mathcal{I}$ inside $B$ (respectively, cover $B$ by the intervals in $mathcal{I}$) by moving $tau$ intervals and keeping the other $sigma = n - tau$ intervals unmoved? We show that both packing and covering are W[1]-hard with any one of $kappa$, $tau$, and $sigma$ as single parameter, but are FPT with combined parameters $kappa$ and $tau$. We also obtain improved polynomial-time algorithms for packing and covering, including an $O(nlog^2 n)$ time algorithm for covering, when all intervals in $mathcal{I}$ have the same length.
In this article, we study shape fitting problems, $epsilon$-coresets, and total sensitivity. We focus on the $(j,k)$-projective clustering problems, including $k$-median/$k$-means, $k$-line clustering, $j$-subspace approximation, and the integer $(j,k)$-projective clustering problem. We derive upper bounds of total sensitivities for these problems, and obtain $epsilon$-coresets using these upper bounds. Using a dimension-reduction type argument, we are able to greatly simplify earlier results on total sensitivity for the $k$-median/$k$-means clustering problems, and obtain positively-weighted $epsilon$-coresets for several variants of the $(j,k)$-projective clustering problem. We also extend an earlier result on $epsilon$-coresets for the integer $(j,k)$-projective clustering problem in fixed dimension to the case of high dimension.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
