# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2212.01620.pdf

(Preprint), 919KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Cslovjecsek, J., Pilipczuk, M., & Węgrzycki, K. (2022). Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments. Retrieved from https://arxiv.org/abs/2212.01620.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1F75-F

##### Abstract

In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are

given a weighted set of $n$ axis-parallel rectangles in the plane. The task is

to find a subset of pairwise non-overlapping rectangles with the maximum

possible total weight. This problem is NP-hard and the best-known

polynomial-time approximation algorithm, due to by Chalermsook and Walczak

(SODA 2021), achieves approximation factor $O(\log\log n )$. While in the

unweighted setting, constant factor approximation algorithms are known, due to

Mitchell (FOCS 2021) and to G\'alvez et al. (SODA 2022), it remains open to

extend these techniques to the weighted setting.

In this paper, we consider MWISR through the lens of parameterized

approximation. Grandoni et al. (ESA 2019) gave a $(1-\epsilon)$-approximation

algorithm with running time $k^{O(k/\epsilon^8)} n^{O(1/\epsilon^8)}$ time,

where $k$ is the number of rectangles in an optimum solution. Unfortunately,

their algorithm works only in the unweighted setting and they left it as an

open problem to give a parameterized approximation scheme in the weighted

setting.

Our contribution is a partial answer to the open question of Grandoni et al.

(ESA 2019). We give a parameterized approximation algorithm for MWISR that

given a parameter $k$, finds a set of non-overlapping rectangles of weight at

least $(1-\epsilon) \text{opt}_k$ in $2^{O(k \log(k/\epsilon))}

n^{O(1/\epsilon)}$ time, where $\text{opt}_k$ is the maximum weight of a

solution of cardinality at most $k$. Note that thus, our algorithm may return a

solution consisting of more than $k$ rectangles. To complement this apparent

weakness, we also propose a parameterized approximation scheme with running

time $2^{O(k^2 \log(k/\epsilon))} n^{O(1)}$ that finds a solution with

cardinality at most $k$ and total weight at least $(1-\epsilon)\text{opt}_k$

for the special case of axis-parallel segments.

given a weighted set of $n$ axis-parallel rectangles in the plane. The task is

to find a subset of pairwise non-overlapping rectangles with the maximum

possible total weight. This problem is NP-hard and the best-known

polynomial-time approximation algorithm, due to by Chalermsook and Walczak

(SODA 2021), achieves approximation factor $O(\log\log n )$. While in the

unweighted setting, constant factor approximation algorithms are known, due to

Mitchell (FOCS 2021) and to G\'alvez et al. (SODA 2022), it remains open to

extend these techniques to the weighted setting.

In this paper, we consider MWISR through the lens of parameterized

approximation. Grandoni et al. (ESA 2019) gave a $(1-\epsilon)$-approximation

algorithm with running time $k^{O(k/\epsilon^8)} n^{O(1/\epsilon^8)}$ time,

where $k$ is the number of rectangles in an optimum solution. Unfortunately,

their algorithm works only in the unweighted setting and they left it as an

open problem to give a parameterized approximation scheme in the weighted

setting.

Our contribution is a partial answer to the open question of Grandoni et al.

(ESA 2019). We give a parameterized approximation algorithm for MWISR that

given a parameter $k$, finds a set of non-overlapping rectangles of weight at

least $(1-\epsilon) \text{opt}_k$ in $2^{O(k \log(k/\epsilon))}

n^{O(1/\epsilon)}$ time, where $\text{opt}_k$ is the maximum weight of a

solution of cardinality at most $k$. Note that thus, our algorithm may return a

solution consisting of more than $k$ rectangles. To complement this apparent

weakness, we also propose a parameterized approximation scheme with running

time $2^{O(k^2 \log(k/\epsilon))} n^{O(1)}$ that finds a solution with

cardinality at most $k$ and total weight at least $(1-\epsilon)\text{opt}_k$

for the special case of axis-parallel segments.