English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the Maximum Independent Set of Rectangles (MISR) problem, where weare given a set of axis-parallel rectangles in the plane and the goal is toselect a subset of non-overlapping rectangles of maximum cardinality. In arecent breakthrough, Mitchell [2021] obtained the first constant-factorapproximation algorithm for MISR. His algorithm achieves an approximation ratioof 10 and it is based on a dynamic program that intuitively recursivelypartitions the input plane into special polygons called corner-clippedrectangles (CCRs), without intersecting certain special horizontal linesegments called fences.  In this paper, we present a $(2+\epsilon)$-approximation algorithm for MISRwhich is also based on a recursive partitioning scheme. First, we use apartition into a class of axis-parallel polygons with constant complexity eachthat are more general than CCRs. This allows us to provide an arguably simpleranalysis and at the same time already improves the approximation ratio to 6.Then, using a more elaborate charging scheme and a recursive partitioning intogeneral axis-parallel polygons with constant complexity, we improve ourapproximation ratio to $2+\epsilon$. In particular, we construct a recursivepartitioning based on more general fences which can be sequences of up to$O(1/\epsilon)$ line segments each. This partitioning routine and our other newideas may be useful for future work towards a PTAS for MISR.

A (2+\epsilon)-Approximation Algorithm for Maximum Independent Set of Rectangles