Grandoni, Fabrizio ;
Kratsch, Stefan ;
Wiese, Andreas
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
Abstract
The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1+epsilon)approximations in f(k,epsilon)n^O(1) time where k is some parameter of the input. The goal is to overcome lower bounds from either of the areas. We obtain the following results on parameterized approximability:
 In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximumcardinality subset of pairwise nonoverlapping rectangles. This problem is NPhard and also W[1]hard [Marx, ESA'05]. The bestknown polynomialtime approximation factor is O(log log n) [Chalermsook and Chuzhoy, SODA'09] and it admits a QPTAS [Adamaszek and Wiese, FOCS'13; Chuzhoy and Ene, FOCS'16]. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant epsilon>0 and integer k>0, in time f(k,epsilon)n^g(epsilon), either outputs a solution of size at least k/(1+epsilon), or declares that the optimum solution has size less than k.
 In the (2dimensional) geometric knapsack problem (2DK) we are given an axisaligned square knapsack and a collection of axisaligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of 2DK with rotations (2DKR), we are allowed to rotate items by 90 degrees. Both variants are NPhard, and the bestknown polynomialtime approximation factor is 2+epsilon [Jansen and Zhang, SODA'04]. These problems admit a QPTAS for polynomially bounded item sizes [Adamaszek and Wiese, SODA'15]. We show that both variants are W[1]hard. Furthermore, we present a PAS for 2DKR.
For all considered problems, getting time f(k,epsilon)n^O(1), rather than f(k,epsilon)n^g(epsilon), would give FPT time f'(k)n^O(1) exact algorithms by setting epsilon=1/(k+1), contradicting W[1]hardness. Instead, for each fixed epsilon>0, our PASs give (1+epsilon)approximate solutions in FPT time.
For both MISR and 2DKR our techniques also give rise to preprocessing algorithms that take n^g(epsilon) time and return a subset of at most k^g(epsilon) rectangles/items that contains a solution of size at least k/(1+epsilon) if a solution of size k exists. This is a special case of the recently introduced notion of a polynomialsize approximate kernelization scheme [Lokshtanov et al., STOC'17].
BibTeX  Entry
@InProceedings{grandoni_et_al:LIPIcs:2019:11174,
author = {Fabrizio Grandoni and Stefan Kratsch and Andreas Wiese},
title = {{Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {53:153:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11174},
URN = {urn:nbn:de:0030drops111741},
doi = {10.4230/LIPIcs.ESA.2019.53},
annote = {Keywords: parameterized approximation, parameterized intractability, independent set of rectangles, geometric knapsack}
}
06.09.2019
Keywords: 

parameterized approximation, parameterized intractability, independent set of rectangles, geometric knapsack 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 