Rectangle covers revisited computationally

ABSTRACT

We consider the problem of covering an orthogonal polygon with a minimum number of axis-parallel rectangles from a computational point of view. We propose an integer program which is the first general approach to obtain provably optimal solutions to this well-studied NP-hard problem. It applies to common variants like covering only the corners or the boundary of the polygon and also to the weighted case. In experiments, it turns out that the linear programming relaxation is extremely tight and rounding a fractional solution is an immediate high-quality heuristic. We obtain excellent experimental results for polygons originating from VLSI design, fax data sheets, black and white images, and for random instances. Making use of the dual linear program, we propose a stronger lower bound on the optimum, namely, the cardinality of a fractional stable set. Furthermore, we outline ideas how to make use of this bound in primal--dual-based algorithms. We give partial results, which make us believe that our proposals have a strong potential to settle the main open problem in the area: To find a constant factor approximation algorithm for the rectangle cover problem.

REFERENCES

• 1: V. S. Anil Kumar , H. Ramesh, Covering Rectilinear Polygons with Axis-Parallel Rectangles, SIAM Journal on Computing, v.32 n.6, p.1509-1541, 2003 [doi>10.1137/S0097539799358835]
• 2: Aupperle, L., Conn, H., Keil, J., and O'Rourke, J. 1988. Covering orthogonal polygons with squares. In Proc. 26th Allerton Conf. Commun. Control Comput. 97--106.
• 3: Berge, C., Chen, C., Chvátal, V., and Seow, C. 1981. Combinatorial properties of polyominoes. Combinatorica 1, 217--224.
• 4: Berman, P. and DasGupta, B. 1997. Complexities of efficient solutions of rectilinear polygon cover problems. Algorithmica 17, 4, 331--356.
• 5: Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 6: Chaiken, S., Kleitman, D., Saks, M., and Shearer, J. 1981. Covering regions by rectangles. SIAM J. Algebraic Discrete Methods 2, 394--410.
• 7: Joseph C. Culberson , Robert A. Reckhow, Covering polygons is hard, Journal of Algorithms, v.17 n.1, p.2-44, July 1994 [doi>10.1006/jagm.1994.1025 ]
• 8: D. S. Franzblau, Performance guarantees on a sweep-line heuristic for covering rectilinear polygons with rectangles, SIAM Journal on Discrete Mathematics, v.2 n.3, p.307-321, August 1989 [doi>10.1137/0402027]
• 9: Goemans, M. and Williamson, D. 1996. The primal-dual method for approximation algorithms and it application to network design problems. See Hochbaum {1996}, Chapter 4.
• 10: Golumbic, M. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.
• 11: Hannenhalli, S., Hubell, E., Lipshutz, R., and Pevzner, P. 2002. Combinatorial algorithms for design of DNA arrays. Adv. Biochem. Eng. Biotechnol. 77, 1--19.
• 12: Heinrich-Litan, L. and Lübbecke, M. 2005. Rectangle covers revisited computationally. In Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA05), S. Nikoletseas, Ed. Lect. Notes Comput. Sci., vol. 3503. Springer-Verlag, New York. 55--66.
• 13: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: ILOG Inc., CPLEX Division. 2004. CPLEX 9.0 User's Manual.
• 15: Jain, K. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 1, 39--60.
• 16: Christos Levcopoulos , Joachim Gudmundsson, Approximation Algorithms for Covering Polygons with Squares and Similar Problems, Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, p.27-41, July 11-12, 1997
• 17: Frédéric Maire, Polyominos and perfect graphs, Information Processing Letters, v.50 n.2, p.57-61, April 22, 1994 [doi>10.1016/0020-0190(94)00017-4 ]
• 18: Masek, W. 1979. Some NP-complete set covering problems. Unpublished manuscript, MIT.
• 19: Rajeev Motwani , A. Raghunathan , Huzur Saran, Covering orthogonal polygons with star polygons: the perfect graph approach, Journal of Computer and System Sciences, v.40 n.1, p.19-48, February 1990 [doi>10.1016/0022-0000(90)90017-F]
• 20: Rajeev Motwani , Arvind Raghunathan , Huzur Saran, Perfect graphs and orthogonally convex covers, SIAM Journal on Discrete Mathematics, v.2 n.3, p.371-392, August 1989 [doi>10.1137/0402033]
• 21: Ohtsuki, T. 1982. Minimum dissection of rectilinear regions. In Proc. 1982 IEEE Symp. on Circuits and Systems, Rome. 1210--1213.
• 22: Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer, New York.
• 23: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Experimentation

Keywords:
Linear programming, integer programming