Document Open Access Logo

How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking

Authors Anna Adamaszek, Parinya Chalermsook, Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.43.pdf
  • Filesize: 0.57 MB
  • 18 pages

Document Identifiers

Author Details

Anna Adamaszek
Parinya Chalermsook
Andreas Wiese

Cite As Get BibTex

Anna Adamaszek, Parinya Chalermsook, and Andreas Wiese. How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 43-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.43

Abstract

In the Maximum Weight Independent Set of Rectangles (MWISR) problem, we are given a collection of weighted axis-parallel rectangles in the plane. Our goal is to compute a maximum weight subset of pairwise non-overlapping rectangles. Due to its various applications, as well as connections to many other problems in computer science, MWISR has received a lot of attention from the computational geometry and the approximation algorithms community. However, despite being extensively studied, MWISR remains not very well understood in terms of polynomial time approximation algorithms, as there is a large gap between the upper and lower bounds, i.e., O(log n\ loglog n) v.s. NP-hardness. Another important, poorly understood question is whether one can color rectangles with at most O(omega(R)) colors where omega(R) is the size of a maximum clique in the intersection graph of a set of input rectangles R. Asplund and Grünbaum obtained an upper bound of O(omega(R)^2) about 50 years ago, and the result has remained asymptotically best.  This question is strongly related to the integrality gap of the canonical LP for MWISR.  

In this paper, we settle above three open problems in a relaxed model where we are allowed to shrink the rectangles by a tiny bit (rescaling them by a factor of 1-delta for an arbitrarily small constant delta > 0. Namely, in this model, we show (i) a PTAS for MWISR and  (ii) a coloring with O(omega(R)) colors which implies a constant upper bound on the integrality gap of the canonical LP. 

For some applications of MWISR the possibility to shrink the rectangles has a natural, well-motivated meaning. Our results can be seen as an evidence that the shrinking model is a promising way to relax a geometric problem for the purpose of better algorithmic results.

Subject Classification

Keywords
  • Approximation algorithms
  • independent set
  • resource augmentation
  • rectangle intersection graphs
  • PTAS

Metrics

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

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, 2013. Google Scholar
  2. Anna Adamaszek and Andreas Wiese. A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 645-656. SIAM, 2014. Google Scholar
  3. Pankaj K. Agarwal and Nabil H. Mustafa. Independent set of intersection graphs of convex objects in 2D. Computational Geometry: Theory and Applications, 34(2):83-95, 2006. Google Scholar
  4. Pankaj K. Agarwal, Marc J. van Kreveld, and Subhash Suri. Label placement by maximum independent set in rectangles. Computational Geometry: Theory and Applications, 11(3-4):209-218, 1998. Google Scholar
  5. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45:753-782, 1998. Google Scholar
  6. E. Asplund and Branko Grünbaum. On a coloring problem. Mathematica Scandinavica, 8:181-188, 1960. Google Scholar
  7. Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, and Suneeta Ramaswami. Improved approximation algorithms for rectangle tiling and packing. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pages 427-436. SIAM, 2001. Google Scholar
  8. A. Bielecki. Problem 56. Colloquium Mathematicum, 1:333, 1948. Google Scholar
  9. Parinya Chalermsook. Coloring and maximum independent set of rectangles. In Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2011), pages 123-134. Springer, 2011. Google Scholar
  10. Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pages 892-901. SIAM, 2009. Google Scholar
  11. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178-189, 2003. Google Scholar
  12. Timothy M. Chan. A note on maximum independent sets in rectangle intersection graphs. Information Processing Letters, 89(1):19-23, 2004. Google Scholar
  13. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. In Proceedings of the 25th Annual Symposium on Computational Geometry (SoCG 2009), pages 333-340. ACM, 2009. Google Scholar
  14. George Christodoulou, Khaled M. Elbassioni, and Mahmoud Fouz. Truthful mechanisms for exhibitions. In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE 2010), pages 170-181. Springer, 2010. Google Scholar
  15. José R. Correa, Laurent Feuilloley, and José A. Soto. Independent and hitting sets of rectangles intersecting a diagonal line. In Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN 2014), pages 35-46. Springer, 2014. Google Scholar
  16. Thomas Erlebach and Klaus Jansen. The complexity of path coloring and call scheduling. Theoretical Computer Science, 255(1-2):33-50, 2001. Google Scholar
  17. 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
  18. Jacob Fox and János Pach. Computing the independence number of intersection graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pages 1161-1165. SIAM, 2011. Google Scholar
  19. Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita, and Takeshi Tokuyama. Data mining with optimized two-dimensional association rules. ACM Transactions on Database Systems (TODS), 26(2):179-213, 2001. Google Scholar
  20. Sariel Har-Peled. Quasi-polynomial time approximation scheme for sparse subsets of polygons. In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), page 120. ACM, 2014. Google Scholar
  21. Sariel Har-Peled and Mira Lee. Weighted geometric set cover problems revisited. JoCG, 3(1):65-85, 2012. Google Scholar
  22. Johan Håstad. Clique is hard to approximate within n^1-ε. Electronic Colloquium on Computational Complexity, 4(38), 1997. Google Scholar
  23. C. Hendler. Schranken für Färbungs-und Cliquenüberdeckungszahl geometrisch repräsentierbarer Graphen. Master’s thesis, FU Berlin, Germany, 1998. Google Scholar
  24. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM, 32(1):130-136, 1985. Google Scholar
  25. Alexandr V. Kostochka. Coloring intersection graphs of geometric figures with a given clique number. Contemporary Mathematics, 342, 2004. Google Scholar
  26. Liane Lewin-Eytan, Joseph Naor, and Ariel Orda. Routing and admission control in networks with advance reservations. In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), pages 215-228. Springer, 2002. Google Scholar
  27. Frank Nielsen. Fast stabbing of boxes in high dimensions. Theoretical Computer Science, 246:53-72, 2000. Google Scholar
  28. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3:103-128, 2007. Google Scholar
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