Document Open Access Logo

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

Authors Fabrizio Grandoni , Stefan Kratsch , Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.53.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Fabrizio Grandoni
  • IDSIA, USI-SUPSI, Manno, Switzerland
Stefan Kratsch
  • Institut für Informatik, Humboldt Universität zu Berlin, Germany
Andreas Wiese
  • Department of Industrial Engineering and Center for Mathematical Modeling, Universidad de Chile, Chile

Funding

  • Grandoni, Fabrizio: Partially supported by the SNSF Excellence Grant 200020B_182865/1.
  • Wiese, Andreas: Partially supported by the Fondecyt Regular grant 1170223.

Cite As Get BibTex

Fabrizio Grandoni, Stefan Kratsch, and Andreas Wiese. Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.53

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 maximum-cardinality subset of pairwise non-overlapping rectangles. This problem is NP-hard and also W[1]-hard [Marx, ESA'05]. The best-known polynomial-time 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 (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+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 polynomial-size approximate kernelization scheme [Lokshtanov et al., STOC'17].

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Fixed parameter tractability
Keywords
  • parameterized approximation
  • parameterized intractability
  • independent set of rectangles
  • geometric knapsack

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Anna Adamaszek and Andreas Wiese. Approximation Schemes for Maximum Weight Independent Set of Rectangles. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 400-409. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.50.
  2. Anna Adamaszek and Andreas Wiese. A quasi-PTAS for the Two-dimensional Geometric Knapsack Problem. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1491-1505. SIAM, 2015. URL: http://dl.acm.org/citation.cfm?id=2722129.2722227.
  3. Cristina Bazgan. Schémas d'approximation et Complexité Paramétrée, Rapport du stage (DEA). Technical report, Universitée Paris Sud, 1995. Google Scholar
  4. Cristina Bazgan, Morgan Chopin, André Nichterlein, and Florian Sikora. Parameterized approximability of maximizing the spread of influence in networks. J. Discrete Algorithms, 27:54-65, 2014. URL: https://doi.org/10.1016/j.jda.2014.05.001.
  5. Cristina Bazgan, Morgan Chopin, André Nichterlein, and Florian Sikora. Parameterized Inapproximability of Target Set Selection and Generalizations. Computability, 3(2):135-145, 2014. URL: https://doi.org/10.3233/COM-140030.
  6. Cristina Bazgan and André Nichterlein. Parameterized Inapproximability of Degree Anonymization. In Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), pages 75-84, 2014. URL: https://doi.org/10.1007/978-3-319-13524-3_7.
  7. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-Approximation Algorithm for Treewidth. SIAM J. Comput., 45(2):317-378, 2016. URL: https://doi.org/10.1137/130947374.
  8. Christina Boucher, Christine Lo, and Daniel Lokshantov. Consensus Patterns (Probably) Has no EPTAS. In Proceedings of the 23rd Annual European Symposium (ESA 2015), pages 239-250, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_21.
  9. Liming Cai and Xiuzhen Huang. Fixed-Parameter Approximation: Conceptual Framework and Approximability Results. In Parameterized and Exact Computation (IWPEC 2006), pages 96-108, 2006. URL: https://doi.org/10.1007/11847250_9.
  10. Marco Cesati and Luca Trevisan. On the Efficiency of Polynomial Time Approximation Schemes. Inf. Process. Lett., 64(4):165-171, 1997. URL: https://doi.org/10.1016/S0020-0190(97)00164-6.
  11. P. Chalermsook and J. Chuzhoy. Maximum independent set of rectangles. In Proceedings of the 20superscriptth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pages 892-901. SIAM, 2009. Google Scholar
  12. Timothy M Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. Google Scholar
  13. Yijia Chen, Martin Grohe, and Magdalena Grüber. On Parameterized Approximability. In Parameterized and Exact Computation (IWPEC 2006), pages 109-120, 2006. URL: https://doi.org/10.1007/11847250_10.
  14. Yijia Chen and Bingkai Lin. The Constant Inapproximability of the Parameterized Dominating Set Problem. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), pages 505-514, 2016. URL: https://doi.org/10.1109/FOCS.2016.61.
  15. Julia Chuzhoy and Alina Ene. On Approximating Maximum Independent Set of Rectangles. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), pages 820-829, 2016. URL: https://doi.org/10.1109/FOCS.2016.92.
  16. Vincent Cohen-Addad and Arnaud de Mesmay. A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface. In Proceedings of the 23rd Annual European Symposium (ESA 2015), pages 386-398, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_33.
  17. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Lower Bounds for Approximation Schemes for Closest String. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), pages 12:1-12:10, 2016. URL: https://doi.org/10.4230/LIPIcs.SWAT.2016.12.
  18. Rodney G. Downey and Michael R. Fellows. Fixed-Parameter Tractability and Completeness II: On Completeness for W[1]. Theor. Comput. Sci., 141(1&2):109-131, 1995. URL: https://doi.org/10.1016/0304-3975(94)00097-3.
  19. Rodney G. Downey, Michael R. Fellows, and Catherine McCartin. Parameterized Approximation Problems. In Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC 2006), pages 121-129, 2006. URL: https://doi.org/10.1007/11847250_11.
  20. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34(6):1302-1323, 2005. Google Scholar
  21. Greg N Federickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing, 16(6):1004-1022, 1987. Google Scholar
  22. Andreas Emil Feldmann. Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), pages 588-600, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_47.
  23. Michael R. Fellows, Ariel Kulik, Frances A. Rosamond, and Hadas Shachnai. Parameterized Approximation via Fidelity Preserving Transformations. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP 2012), pages 351-362, 2012. URL: https://doi.org/10.1007/978-3-642-31594-7_30.
  24. Robert J Fowler, Michael S Paterson, and Steven L Tanimoto. Optimal packing and covering in the plane are NP-complete. Information processing letters, 12(3):133-137, 1981. Google Scholar
  25. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating Geometric Knapsack via L-Packings. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 260-271, 2017. URL: https://doi.org/10.1109/FOCS.2017.32.
  26. Sandy Heydrich and Andreas Wiese. Faster approximation schemes for the two-dimensional knapsack problem. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 79-98. SIAM, 2017. Google Scholar
  27. Klaus Jansen and Roberto Solis-Oba. A polynomial time approximation scheme for the square packing problem. In International Conference on Integer Programming and Combinatorial Optimization, pages 184-198. Springer, 2008. Google Scholar
  28. Klaus Jansen and Guochaun Zhang. On rectangle packing: maximizing benefits. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 204-213. SIAM, 2004. Google Scholar
  29. Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, and Saket Saurabh. Parameterized Approximations via d-Skew-Symmetric Multicut. In Proceedings of the 39th International Symposium (MFCS 2014), pages 457-468, 2014. URL: https://doi.org/10.1007/978-3-662-44465-8_39.
  30. Michael Lampis. Parameterized Approximation Schemes Using Graph Widths. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), pages 775-786, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_64.
  31. Joseph YT Leung, Tommy W Tam, Chin S Wong, Gilbert H Young, and Francis YL Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3):271-275, 1990. Google Scholar
  32. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 224-237, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  33. Dániel Marx. Efficient Approximation Schemes for Geometric Problems? In Algorithms - Proceedings of ESA 2005, pages 448-459, 2005. URL: https://doi.org/10.1007/11561071_41.
  34. Dániel Marx. Parameterized Complexity and Approximation Algorithms. Comput. J., 51(1):60-78, 2008. URL: https://doi.org/10.1093/comjnl/bxm048.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact