{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T20:54:38Z","timestamp":1770324878092,"version":"3.49.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T00:00:00Z","timestamp":1170979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2007,2,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1187436.1216583","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":5,"title":["Rectangle covers revisited computationally"],"prefix":"10.1145","volume":"11","author":[{"given":"Laura","family":"Heinrich-Litan","sequence":"first","affiliation":[{"name":"Robert Bosch GmbH, Daimlerstrasse, Leonberg"}]},{"given":"Marco E.","family":"L\u00fcbbecke","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2007,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799358835"},{"key":"e_1_2_1_2_1","volume-title":"Proc. 26th Allerton Conf. Commun. Control Comput. 97--106","author":"Aupperle L.","year":"1988","unstructured":"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 .]] 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.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF02579327","article-title":"Combinatorial properties of polyominoes","volume":"1","author":"Berge C.","year":"1981","unstructured":"Berge , C. , Chen , C. , Chv\u00e1tal , V. , and Seow , C. 1981 . Combinatorial properties of polyominoes . Combinatorica 1 , 217 -- 224 .]] Berge, C., Chen, C., Chv\u00e1tal, V., and Seow, C. 1981. Combinatorial properties of polyominoes. Combinatorica 1, 217--224.]]","journal-title":"Combinatorica"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF02523677","article-title":"Complexities of efficient solutions of rectilinear polygon cover problems","volume":"17","author":"Berman P.","year":"1997","unstructured":"Berman , P. and DasGupta , B. 1997 . Complexities of efficient solutions of rectilinear polygon cover problems . Algorithmica 17 , 4, 331 -- 356 .]] Berman, P. and DasGupta, B. 1997. Complexities of efficient solutions of rectilinear polygon cover problems. Algorithmica 17, 4, 331--356.]]","journal-title":"Algorithmica"},{"key":"e_1_2_1_5_1","first-page":"296","article-title":"Approximation algorithms for geometric problems. See Hochbaum {1996}","volume":"8","author":"Bern M.","year":"1997","unstructured":"Bern , M. and Eppstein , D. 1997 . Approximation algorithms for geometric problems. See Hochbaum {1996} , Chapter 8 , 296 -- 345 .]] Bern, M. and Eppstein, D. 1997. Approximation algorithms for geometric problems. See Hochbaum {1996}, Chapter 8, 296--345.]]","journal-title":"Chapter"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1137\/0602042","article-title":"Covering regions by rectangles","volume":"2","author":"Chaiken S.","year":"1981","unstructured":"Chaiken , S. , Kleitman , D. , Saks , M. , and Shearer , J. 1981 . Covering regions by rectangles . SIAM J. Algebraic Discrete Methods 2 , 394 -- 410 .]] Chaiken, S., Kleitman, D., Saks, M., and Shearer, J. 1981. Covering regions by rectangles. SIAM J. Algebraic Discrete Methods 2, 394--410.]]","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1025"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402027"},{"key":"e_1_2_1_9_1","unstructured":"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.]]  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.]]"},{"key":"e_1_2_1_10_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M.","unstructured":"Golumbic , M. 1980. Algorithmic Graph Theory and Perfect Graphs . Academic Press , New York .]] Golumbic, M. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.]]"},{"key":"e_1_2_1_11_1","first-page":"1","article-title":"Combinatorial algorithms for design of DNA arrays","volume":"77","author":"Hannenhalli S.","year":"2002","unstructured":"Hannenhalli , S. , Hubell , E. , Lipshutz , R. , and Pevzner , P. 2002 . Combinatorial algorithms for design of DNA arrays . Adv. Biochem. Eng. Biotechnol. 77 , 1 -- 19 .]] Hannenhalli, S., Hubell, E., Lipshutz, R., and Pevzner, P. 2002. Combinatorial algorithms for design of DNA arrays. Adv. Biochem. Eng. Biotechnol. 77, 1--19.]]","journal-title":"Adv. Biochem. Eng. Biotechnol."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA05)","volume":"3503","author":"Heinrich-Litan L.","unstructured":"Heinrich-Litan , L. and L\u00fcbbecke , 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.]] 10.1007\/11427186_7 Heinrich-Litan, L. and L\u00fcbbecke, 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.]] 10.1007\/11427186_7"},{"key":"e_1_2_1_13_1","volume-title":"1996. Approximation Algorithms for NP-Hard Problems","author":"Hochbaum D.","unstructured":"Hochbaum , D. , Ed. 1996. Approximation Algorithms for NP-Hard Problems . PWS , Boston, MA .]] Hochbaum, D., Ed. 1996. Approximation Algorithms for NP-Hard Problems. PWS, Boston, MA.]]"},{"key":"e_1_2_1_14_1","unstructured":"ILOG Inc. CPLEX Division. 2004. CPLEX 9.0 User's Manual.]]  ILOG Inc. CPLEX Division. 2004. CPLEX 9.0 User's Manual.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s004930170004","article-title":"A factor 2 approximation algorithm for the generalized Steiner network problem","volume":"21","author":"Jain K.","year":"2001","unstructured":"Jain , K. 2001 . A factor 2 approximation algorithm for the generalized Steiner network problem . Combinatorica 21 , 1, 39 -- 60 .]] Jain, K. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 1, 39--60.]]","journal-title":"Combinatorica"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of RANDOM'97","volume":"1269","author":"Levcopoulos C.","unstructured":"Levcopoulos , C. and Gudmundsson , J . 1997. Approximation algorithms for covering polygons with squares and similar problems . In Proceedings of RANDOM'97 . Lect. Notes Comput. Sci. , vol. 1269 . Springer, New York. 27--41.]] Levcopoulos, C. and Gudmundsson, J. 1997. Approximation algorithms for covering polygons with squares and similar problems. In Proceedings of RANDOM'97. Lect. Notes Comput. Sci., vol. 1269. Springer, New York. 27--41.]]"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00017-4"},{"key":"e_1_2_1_18_1","unstructured":"Masek W. 1979. Some NP-complete set covering problems. Unpublished manuscript MIT.]]  Masek W. 1979. Some NP-complete set covering problems. Unpublished manuscript MIT.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90017-F"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402033"},{"key":"e_1_2_1_21_1","volume-title":"Proc. 1982 IEEE Symp. on Circuits and Systems","author":"Ohtsuki T.","year":"1982","unstructured":"Ohtsuki , T. 1982 . Minimum dissection of rectilinear regions . In Proc. 1982 IEEE Symp. on Circuits and Systems , Rome. 1210--1213.]] Ohtsuki, T. 1982. Minimum dissection of rectilinear regions. In Proc. 1982 IEEE Symp. on Circuits and Systems, Rome. 1210--1213.]]"},{"key":"e_1_2_1_22_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003","unstructured":"Schrijver , A. 2003 . Combinatorial Optimization: Polyhedra and Efficiency . Springer , New York .]] Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer, New York.]]"},{"key":"e_1_2_1_23_1","volume-title":"Approximation Algorithms","author":"Vazirani V.","unstructured":"Vazirani , V. 2001. Approximation Algorithms . Springer , New York .]] Vazirani, V. 2001. Approximation Algorithms. Springer, New York.]]"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1216583","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187436.1216583","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:11Z","timestamp":1750262891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1216583"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,9]]},"references-count":23,"alternative-id":["10.1145\/1187436.1216583"],"URL":"https:\/\/doi.org\/10.1145\/1187436.1216583","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2,9]]}}}