Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments

In this paper, we consider \textsc{MWISR} through the lens of parameterized approximation. Grandoni et~al. (ESA 2019) gave $(1-\eps)$-approximation algorithm with running time $k^{\mathcal{O}(k/\eps^8)} n^{\mathcal{O}(1/\eps^8)}$ time, where $k$ is the number of rectangles in optimum solution. Unfortunately, their algorithm only works 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 \textsc{MWISR} that given a parameter $k \in \nat$, finds a set of non-overlapping rectangles of weight at least $(1-\eps) \omega(\mathrm{opt}_k)$ in $2^{\mathcal{O}(k \log(k/\eps))} n^{\mathcal{O}(1/\eps)}$ time, where $\omega(\mathrm{opt}_k)$ is the maximum weight of 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 that outputs a solution with cardinality at most $k$ and total weight at least $(1-\eps)\omega(\mathrm{opt}_k)$ for the special case of axis-parallel segments.

Joint work with Jana Cslovjecsek and Michał Pilipczuk