Summary: The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., \((1+\varepsilon)\)-approximations in \(f(k,\varepsilon)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 maximum-cardinality subset of pairwise non-overlapping rectangles. This problem is NP-hard and also W[1]-hard [D. Marx, Lect. Notes Comput. Sci. 3669, 448–459 (2005; Zbl 1162.68822)]. The best-known polynomial-time approximation factor is \(O(\log\log n)\) [D. Marx, Lect. Notes Comput. Sci. 3669, 448–459 (2005; Zbl 1162.68822)] and it admits a QPTAS [A. Adamaszek and A. Wiese, in: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 400–409. IEEE Computer Society, 2013. doi:10.1109/FOCS.2013.50; J. Chuzhoy and A. Ene, In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), pages 820–829 (2016; doi:10.1109/FOCS.2016.92)]. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant \(\varepsilon>0\) and integer \(k>0\), in time \(f(k,\varepsilon)n^{g(\varepsilon)}\), either outputs a solution of size at least \(k/(1+\varepsilon)\), or declares that the optimum solution has size less than \(k\).

–

In the (\(2\)-dimensional) geometric knapsack problem (2DK) we are given an axis-aligned square knapsack and a collection of axis-aligned 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 NP-hard, and the best-known polynomial-time approximation factor is \(2+\varepsilon\) [K. Jansen and G. Zhang, in: Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11–13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 204–213 (2004; Zbl 1317.68280)]. These problems admit a QPTAS for polynomially bounded item sizes [A. Adamaszek and A. Wiese, in: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1491–1505 (2015; Zbl 1371.90115)]. We show that both variants are W[1]-hard. Furthermore, we present a PAS for 2DKR.

For all considered problems, getting time \(f(k,\varepsilon)n^{O(1)}\), rather than \(f(k,\varepsilon)n^{g(\varepsilon)}\), would give FPT time \(f'(k)n^{O(1)}\) exact algorithms by setting \(\varepsilon=1/(k+1)\), contradicting W[1]-hardness. Instead, for each fixed \(\varepsilon>0\), our PASs give \((1+\varepsilon)\)-approximate solutions in FPT time.
For both MISR and 2DKR our techniques also give rise to preprocessing algorithms that take \(n^{g(\varepsilon)}\) time and return a subset of at most \(k^{g(\varepsilon)}\) rectangles/items that contains a solution of size at least \(k/(1+\varepsilon)\) if a solution of size \(k\) exists. This is a special case of the recently introduced notion of a polynomial-size approximate kernelization scheme [D. Lokshtanov et al., in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM). 224–237 (2017; Zbl 1370.68136)].
For the entire collection see [Zbl 1423.68016].