Inhalt des Dokuments
Preprint 37-2004
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Rectangle Covers Revisited Computationally
- Authors
- Classification
-
MSC: primary: 90C27 Combinatorial optimization secondary: 90C10 Integer programming 68Q25 Analysis of algorithms and problem complexity - Keywords
-
Orthogonal polygon; rectangle cover; integer program; approximation algorithm
- Abstract
-
We consider the problem of covering an orthogonal polygon with a minimum number of axis-parallel rectangles from a computational point of view. Our integer programming formulation is the first approach to solve this NP-hard problem optimally. In experiments it turns out that the linear programming relaxation is extremely tight. Making use of the dual program, we propose a new lower bound on the optimum, namely the cardinality of a fractional stable set. We obtain excellent experimental results for polygons originating from VLSI design, fax data sheets, black and white images, and for random instances. We 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.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe