Campus Event Calendar

Event Entry

What and Who

Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments

Karol Węgrzycki
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Thursday, 23 February 2023
30 Minutes
E1 4


In the \textsc{Maximum Weight Independent Set of Rectangles} problem (\textsc{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 $\mathcal{O}(\log\log(n))$. While in the unweighted setting, constant factor approximation algorithms are known, due to Mitchell (FOCS 2021) and to Gálvez et al. (SODA 2022), it remains open to extend these techniques to the weighted setting.

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


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 02/16/2023 10:04 -- Created document.