Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeometric Dominating Set and Set Cover via Local Search
128
0
0.0
(
0
)
Added by
Minati De
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study two classic optimization problems: minimum geometric dominating set and set cover. Both the problems have been studied for different types of objects for a long time. These problems become APX-hard when the objects are axis-parallel rectangles, ellipses, $alpha$-fat objects of constant description complexity, and convex polygons. On the other hand, PTAS (polynomial time approximation scheme) is known for them when the objects are disks or unit squares. Surprisingly, PTAS was unknown even for arbitrary squares. For homothetic set of convex objects, an $O(k^4)$ approximation algorithm is known for dominating set problem, where $k$ is the number of corners in a convex object. On the other hand, QPTAS (quasi polynomial time approximation scheme) is known very recently for the covering problem when the objects are pseudodisks. For both problems obtaining a PTAS remains open for a large class of objects. For the dominating set problems, we prove that the popular local search algorithm leads to an $(1+varepsilon)$ approximation when objects are homothetic set of convex objects (which includes arbitrary squares, $k$-regular polygons, translated and scaled copies of a convex set etc.) in $n^{O(1/varepsilon^2)}$ time. On the other hand, the same technique leads to a PTAS for geometric covering problem when the objects are convex pseudodisks (which includes disks, unit height rectangles, homothetic convex objects etc.). As a consequence, we obtain an easy to implement approximation algorithm for both problems for a large class of objects, significantly improving the best known approximation guarantees.
rate research
Read More
We improve the running times of $O(1)$-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized $O(nlog^4 n)$-time, $O(1)$-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic $O(nlog^3 nloglog n)$-time algorithm. With further new ideas, we obtain a still faster randomized $O(nlog n(loglog n)^{O(1)})$-time algorithm. For the weighted problem, we also give a randomized $O(nlog^4nloglog n)$-time, $O(1)$-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.
Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset of vertices $Dsubseteq V$ such that every vertex $uin Vsetminus D$ is adjacent to at least one vertex $vin D$. That is, the set $D$ satisfies the condition that $|N[v]cap D|geq 1$ for each $vin V$, where $N[v]$ is the closed neighborhood of $v$. In this paper, we study two variants of the classical dominating set problem: $boldmath{k}$-tuple dominating set ($k$-DS) problem and Liars dominating set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor ($frac{11}{2}$)-approximation algorithm for the Liars dominating set problem on unit disk graphs. Then, we obtain a PTAS for the $boldmath{k}$-tuple dominating set problem on unit disk graphs. On the hardness side, we show a $Omega (n^2)$ bits lower bound for the space complexity of any (randomized) streaming algorithm for Liars dominating set problem as well as for the $boldmath{k}$-tuple dominating set problem. Furthermore, we prove that the Liars dominating set problem on bipartite graphs is W[2]-hard.
We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an $O(1)$-approximation in sublinear update time for set cover for axis-aligned squares in 2D. More precisely, we obtain randomized update time $O(n^{2/3+delta})$ for an arbitrarily small constant $delta>0$. Previously, a dynamic geometric set cover data structure with sublinear update time was known only for unit squares by Agarwal, Chang, Suri, Xiao, and Xue [SoCG 2020]. If only an approximate size of the solution is needed, then we can also obtain sublinear amortized update time for disks in 2D and halfspaces in 3D. As a byproduct, our techniques for dynamic set cover also yield an optimal randomized $O(nlog n)$-time algorithm for static set cover for 2D disks and 3D halfspaces, improving our earlier $O(nlog n(loglog n)^{O(1)})$ result [SoCG 2020].
We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most $s$ and each element is contained in at most $t$ sets, the algorithm reports whether a given set is in some fixed set cover whose expected size is $O(log{s})$ times the minimum fractional set cover value. Our algorithm requires $s^{O(log{s})} t^{O(log{s} cdot (log log{s} + log log{t}))}$ queries. This result improves upon the application of the reduction of [Parnas and Ron, TCS07] on the result of [Kuhn et al., SODA06], which leads to a query complexity of $(st)^{O(log{s} cdot log{t})}$. To obtain this result, we design a parallel set cover algorithm that admits an efficient simulation in the LCA model by using a sparsification technique introduced in [Ghaffari and Uitto, SODA19] for the maximal independent set problem. The parallel algorithm adds a random subset of the sets to the solution in a style similar to the PRAM algorithm of [Berger et al., FOCS89]. However, our algorithm differs in the way that it never revokes its decisions, which results in a fewer number of adaptive rounds. This requires a novel approximation analysis which might be of independent interest.
This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. We consider important graph classes, distinguishing between connected and not necessarily connected graphs. For the classic graph classes of trees, bipartite, planar, and general graphs, we obtain tight results in almost all cases. We also derive upper and lower bounds for the class of bounded-degree graphs. From these analyses, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithms disadvantage.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
