Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Rectangle Covers Revisited Computationally
Author(s): Heinrich-Litan, Laura
Lübbecke, Marco E.
Type: Research Paper
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.
Subject(s): orthogonal polygon
rectangle cover
integer program
approximation algorithm
Issue Date: 2004
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C27 Combinatorial optimization
90C10 Integer programming
68Q25 Analysis of algorithms and problem complexity
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2004, 37
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 432.14 kB
DownloadShow Preview
Format: Unknown | Size: 416.84 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.