Access Restriction

Author Heinrich-Litan, Laura ♦ Lbbecke, Marco E.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Linear programming ♦ Integer programming
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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-02-09
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 11

Open content in new tab

   Open content in new tab
Source: ACM Digital Library