Maximum independent set of rectangles

ABSTRACT

We study the Maximum Independent Set of Rectangles (MISR) problem: given a collection R of n axis-parallel rectangles, find a maximum-cardinality subset of disjoint rectangles. MISR is a special case of the classical Maximum Independent Set problem, where the input is restricted to intersection graphs of axis-parallel rectangles. Due to its many applications, ranging from map labeling to data mining, MISR has received a significant amount of attention from various research communities. Since the problem is NP-hard, the main focus has been on the design of approximation algorithms. Several groups of researches have independently suggested O(log n)-approximation algorithms for MISR, and this remained the best currently known approximation factor for the problem. The main result of our paper is an O(log log n)-approximation algorithm for MISR. Our algorithm combines existing approaches for solving special cases of the problem, in which the input set of rectangles is restricted to containing specific intersection types, with new insights into the combinatorial structure of sets of intersecting rectangles in the plane.

We also consider a generalization of MISR to higher dimensions, where rectangles are replaced by d-dimensional hyper-rectangles. Our results for MISR imply an O((log n)^d−2 log log ⁿ)-approximation algorithm for this problem, improving upon the best previously known O((log n)^d−1)-approximation.

REFERENCES

• 1: Pankaj K. Agarwal , Marc van Kreveld , Subhash Suri, Label placement by maximum independent set in rectangles, Computational Geometry: Theory and Applications, v.11 n.3-4, p.209-218, Dec. 1998
• 2: Piotr Berman , Bhaskar DasGupta , S. Muthukrishnan , Suneeta Ramaswami, Improved approximation algorithms for rectangle tiling and packing, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.427-436, January 07-09, 2001, Washington, D.C., United States
• 3: Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
• 4: Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003 [doi>10.1016/S0196-6774(02)00294-8]
• 5: T. M. Chan. A note on maximum independent sets in rectangle intersection graphs. Information Processing Letters, Volume 89, Number 1, pp. 19--23, 2004.
• 6: L. S. Chandran, M. C. Francis and N. Sivadasa. Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes. Algorithmica, to appear.
• 7: L. S. Chandran, M. C. Francis, and N. Sivadasan. Boxicity and maximum degree. Journal of Combinatorial Theory Series B (2007).
• 8: L. Sunil Chandran , Naveen Sivadasan, Boxicity and treewidth, Journal of Combinatorial Theory Series B, v.97 n.5, p.733-744, September, 2007 [doi>10.1016/j.jctb.2006.12.004]
• 9: Miroslav Chlebík , Janka Chlebíková, Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: M. B. Cozzens. Higher and multidimensional analogues of interval graphs. Ph.D. thesis, Rutgers University, New Brunswick, NJ (1981).
• 11: Jeffrey S. Doerschler , Herbert Freeman, A rule-based system for dense-map name placement, Communications of the ACM, v.35 n.1, p.68-79, Jan. 1992 [doi>10.1145/129617.129620]
• 12: Thomas Erlebach , Klaus Jansen , Eike Seidel, Polynomial-Time Approximation Schemes for Geometric Intersection Graphs, SIAM Journal on Computing, v.34 n.6, p.1302-1323, 2005 [doi>10.1137/S0097539702402676]
• 13: R. J. Fowler, M. S. Paterson and S. L. Tanimoto, Optimal packing and covering in the plane are NP-complete. Information Processing Letter. 12 3 (1981), pp. 133137.
• 14: Takeshi Fukuda , Yasuhiko Morimoto , Shimichi Morishita , Takeshi Tokuyama, Data Mining with optimized two-dimensional association rules, ACM Transactions on Database Systems (TODS), v.26 n.2, p.179-213, June 2001 [doi>10.1145/383891.383893]
• 15: A. G. Greenberg and D. Wischik. Admission Control for Booking Ahead Shared Resources, In Proceedings IEEE INFOCOM '98, pp. 873--882, 1998.
• 16: R. A. Guerin and A. Orda. Networks with advance reservations: The routing perspective. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2000.
• 17: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 18: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 19: H. Imai, T. Asano. Finding the Connected Components and a Maximum Clique of an Intersection Graph of Rectangles in the Plane. Journal of Algorithms 4(4): 310--323, 1983.
• 20: Sanjeev Khanna , S. Muthukrishnan , Mike Paterson, On approximating rectangle tiling and packing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.384-393, January 25-27, 1998, San Francisco, California, United States
• 21: Jan Kratochvíl, A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Applied Mathematics, v.52 n.3, p.233-252, Aug. 26, 1994 [doi>10.1016/0166-218X(94)90143-0]
• 22: Brian Lent , Arun N. Swami , Jennifer Widom, Clustering Association Rules, Proceedings of the Thirteenth International Conference on Data Engineering, p.220-231, April 07-11, 1997
• 23: Liane Lewin-Eytan , Joseph (Seffi) Naor , Ariel Orda, Routing and Admission Control in Networks with Advance Reservations, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.215-228, September 17-21, 2002
• 24: Andrzej Lingas , Martin Wahlen, A note on maximum independent set and related problems on box graphs, Information Processing Letters, v.93 n.4, p.169-171, 28 February 2005 [doi>10.1016/j.ipl.2004.10.013]
• 25: Frank Nielsen, Fast stabbing of boxes in high dimensions, Theoretical Computer Science, v.246 n.1-2, p.53-75, Sept 2000 [doi>10.1016/S0304-3975(98)00336-3]
• 26: F. S. Roberts. On the boxicity and Cubicity of a graph. In: Recent Progresses in Combinatorics, pp. 301--310. Academic, New York (1969).
• 27: B. Rosgen, L. Stewart. Complexity results on graphs with few cliques. Discrete Math. Theor. Comput. Sci. 9, 127136 (2007) 21. Scheinerman, E. R.: Intersection
• 28: E. R. Scheinerman, Intersection classes and multiple intersection parameters. Ph.D. thesis, Princeton University (1984).
• 29: Olov Schelén , Stephen Pink, Resource sharing in advance reservation agents, Journal of High Speed Networks, v.7 n.3-4, p.213-228, December 1998
• 30: A. Schill , Sabine Kühn , Frank Breiter, Design and evaluation of an advance reservation protocol on top of RSVP, Proceedings of the IFIP TC6/WG6.2 Fourth International Conference on Broadband Communications: The future of telecommunications, p.23-40, April 01-03, 1998
• 31: Carsten Thomassen, Interval representations of planar graphs, Journal of Combinatorial Theory Series B, v.40 n.1, p.9-20, Feb. 1986 [doi>10.1016/0095-8956(86)90061-4]
• 32: Mihalis Yannakakis. The complexity of the partial order dimension problem. SIAM Journal on Algebraic Discrete Methods, 3(3):351--358, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms