2026-07-25T16:22:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21114 2024-09-23T09:13:17Z ddc:004 open_access

Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments Cslovjecsek, Jana Pilipczuk, Michał Węgrzycki, Karol parameterized approximation Maximum Weight Independent Set rectangles 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 𝒪(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 MWISR through the lens of parameterized approximation. Grandoni, Kratsch and Wiese [ESA 2019] gave a (1-ε)-approximation algorithm running in k^{𝒪(k/ε⁸)} n^{𝒪(1/ε⁸)} 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 ∈ ℕ, finds a set of non-overlapping rectangles of weight at least (1-ε) opt_k in 2^{𝒪(k log(k/ε))} n^{𝒪(1/ε)} 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^{𝒪(k² log(k/ε))} n^{𝒪(1)} that finds a solution with cardinality at most k and total weight at least (1-ε)opt_k for the special case of axis-parallel segments. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jana Cslovjecsek and Michał Pilipczuk and Karol Węgrzycki 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.43 urn:nbn:de:0030-drops-211146 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.43 eng https://creativecommons.org/licenses/by/4.0/legalcode