Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximating Maximum Independent Set for Rectangles in the Plane
144
0
0.0
(
0
)
Added by
Joseph S. B. Mitchell
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Joseph S. B. Mitchell
Ask ChatGPT about the research
No Arabic abstract
We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is $O(loglog n)$. The results are based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursively partitioned into a constant number of such faces.
rate research
Read More
We study the Maximum Independent Set of Rectangles (MISR) problem: given a set of $n$ axis-parallel rectangles, find a largest-cardinality subset of the rectangles, such that no two of them overlap. MISR is a basic geometric optimization problem with many applications, that has been studied extensively. Until recently, the best approximation algorithm for it achieved an $O(log log n)$-approximation factor. In a recent breakthrough, Adamaszek and Wiese provided a quasi-polynomial time approximation scheme: a $(1-epsilon)$-approximation algorithm with running time $n^{O(operatorname{poly}(log n)/epsilon)}$. Despite this result, obtaining a PTAS or even a polynomial-time constant-factor approximation remains a challenging open problem. In this paper we make progress towards this goal by providing an algorithm for MISR that achieves a $(1 - epsilon)$-approximation in time $n^{O(operatorname{poly}(loglog{n} / epsilon))}$. We introduce several new technical ideas, that we hope will lead to further progress on this and related problems.
In 1960, Asplund and Grunbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an $O(omega^2)$-coloring, where $omega$ is the maximum size of a clique. We present the first asymptotic improvement over this six-decade-old bound, proving that every such graph is $O(omegalogomega)$-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time $O(loglog n)$-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of $O(frac{log n}{loglog n})$.
We present improved results for approximating maximum-weight independent set ($MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let $n$ and $Delta$ be the number of nodes and maximum degree, respectively, and let $MIS(n,Delta)$ be the the running time of finding a emph{maximal} independent set ($MIS$) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a $Delta$-approximation for $MaxIS$ in $O(MIS(n,Delta)log W)$ rounds, where $W$ is the maximum weight of a node in the graph, which can be as high as $poly (n)$. Whether their algorithm is deterministic or randomized depends on the $MIS$ algorithm that is used as a black-box. Our main result in this work is a randomized $(poly(loglog n)/epsilon)$-round algorithm that finds, with high probability, a $(1+epsilon)Delta$-approximation for $MaxIS$ in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an emph{exponential} speed-up in the running time over the previous best known result. Due to a lower bound of $Omega(sqrt{log n/log log n})$ that was given by Kuhn, Moscibroda and Wattenhofer [JACM, 2016] on the number of rounds for any (possibly randomized) algorithm that finds a maximal independent set (even in the LOCAL model) this result implies that finding a $(1+epsilon)Delta$-approximation for $MaxIS$ is exponentially easier than $MIS$.
Maximum independent set from a given set $D$ of unit disks intersecting a horizontal line can be solved in $O(n^2)$ time and $O(n^2)$ space. As a corollary, we design a factor 2 approximation algorithm for the maximum independent set problem on unit disk graph which takes both time and space of $O(n^2)$. The best known factor 2 approximation algorithm for this problem runs in $O(n^2 log n)$ time and takes $O(n^2)$ space [Jallu and Das 2016, Das et al. 2016].
We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present data structures that maintain a constant-factor approximate maximum independent set for broad classes of fat objects in $d$ dimensions, where $d$ is assumed to be a constant, in sublinear textit{worst-case} update time. This gives the first results for dynamic independent set in a wide variety of geometric settings, such as disks, fat polygons, and their high-dimensional equivalents. For axis-aligned squares and hypercubes, our result improves upon all (recently announced) previous works. We obtain, in particular, a dynamic $(4+epsilon)$-approximation for squares, with $O(log^4 n)$ worst-case update time. Our result is obtained via a two-level approach. First, we develop a dynamic data structure which stores all objects and provides an approximate independent set when queried, with output-sensitive running time. We show that via standard methods such a structure can be used to obtain a dynamic algorithm with textit{amortized} update time bounds. Then, to obtain worst-case update time algorithms, we develop a generic deamortization scheme that with each insertion/deletion keeps (i) the update time bounded and (ii) the number of changes in the independent set constant. We show that such a scheme is applicable to fat objects by showing an appropriate generalization of a separator theorem. Interestingly, we show that our deamortization scheme is also necessary in order to obtain worst-case update bounds: If for a class of objects our scheme is not applicable, then no constant-factor approximation with sublinear worst-case update time is possible. We show that such a lower bound applies even for seemingly simple classes of geometric objects including axis-aligned rectangles in the plane.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
