اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدApproximating Maximum Independent Set for Rectangles in the Plane
144
0
0.0
(
0
)
نشر من قبل
Joseph S. B. Mitchell
تاريخ النشر
2021
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
تأليف
Joseph S. B. Mitchell
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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-deca
de-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 le
t $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 f
at 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
