Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments

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 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 Galvez 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, Kratsch and Wiese [ESA 2019] gave a (1 - epsilon)-approximation algorithm running in 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. We give a parameterized approximation algorithm for MWISR that given a parameter k epsilon N, finds a set of non-overlapping rectangles of weight at least (1 - epsilon)opt(k) in 2(O(k log(k/epsilon))) n(O(1/epsilon)) time, where opt(k) is the maximum weight of a solution of cardinality at most k. We also propose a parameterized approximation scheme with running time 2(O(k2 log(k/epsilon))) n(O(1)) that finds a solution with cardinality at most k and total weight at least (1 - epsilon)opt(k) for the special case of axis-parallel segments.