Access the full text.
Sign up today, get DeepDyve free for 14 days.
Formulate the null hypotesis according to which the theoretical median of f S 1 (I )− f S 2 (I ) = 0 (i.e., both heuristic variants are not significantly different)
Hervé Brönnimann, M. Goodrich (1995)
Almost optimal set covers in finite VC-dimensionDiscrete & Computational Geometry, 14
S. Hannenhalli, Earl Hubell, R. Lipshutz, P. Pevzner (2002)
Combinatorial algorithms for design of DNA arrays.Advances in biochemical engineering/biotechnology, 77
(1979)
Some NP-complete set covering problems
S. Chaiken, D. Kleitman, M. Saks, J. Shearer (1981)
Covering Regions by RectanglesSiam Journal on Algebraic and Discrete Methods, 2
Compute the gap of the results of Scenario I and Scenario II for the instances of I , obtaining a collection of pair values ( f S 1
David Applegate, G. Călinescu, David Johnson, H. Karloff, Katrina Ligett, Jia Wang (2007)
Compressing rectilinear pictures and minimizing access control lists
Shangliang Jiang, A. Zakhor (2014)
Shot overlap model-based fracturing for edge-based OPC layouts, 9052
David Johnson (1973)
Approximation algorithms for combinatorial problemsProceedings of the fifth annual ACM symposium on Theory of computing
P. Berman, B. Dasgupta (1997)
Complexities of efficient solutions of rectilinear polygon cover problemsAlgorithmica, 17
L. Lovász (1975)
On the ratio of optimal integral and fractional coversDiscret. Math., 13
R. Motwani, A. Raghunathan, H. Saran (1988)
Covering orthogonal polygons with star polygons: the perfect graph approachJ. Comput. Syst. Sci., 40
N. Japkowicz, Mohak Shah (2011)
Evaluating Learning Algorithms: A Classification Perspective
V. Soltan, Alexei Gorpinevich (1992)
Minimum dissection of rectilinear polygon with arbitrary holes into rectangles
G. Scheithauer, Y. Stoyan, T. Romanova (2009)
Integer Linear Programming Models for the Problem of Covering a Polygonal Region by Rectangles
Laura Heinrich-Litan, M. Lübbecke (2005)
Rectangle covers revisited computationallyJournal of Experimental Algorithmics (JEA), 11
TB Chan, P Gupta, K Han, AA Kagalwalla, AB Kahng (2017)
Benchmarking of mask fracturing heuristicsTrans Comput Aided Design Integr Circuits Syst, 36
DS Johnson (1974)
Approximation algorithms for combinatorial problemsJ Comput Syst Sci, 9
Shangliang Jiang, A. Zakhor (2011)
Application of signal reconstruction techniques to shot count reduction in simulation driven fracturing, 8166
C. Levcopoulos, Joachim Gudmundsson (1997)
Approximation Algorithms for Covering Polygons with Squares and Similar Problems
R. Motwani, A. Raghunathan, H. Saran (1989)
Perfect Graphs and Orthogonally Convex CoversSIAM J. Discret. Math., 2
V. Kumar, H. Ramesh (1999)
Covering rectilinear polygons with axis-parallel rectanglesSIAM J. Comput., 32
A. Hegedüs (1982)
Algorithms for covering polygons by rectanglesComputer-aided Design, 14
A. Kagalwalla, Puneet Gupta (2015)
Effective model-based mask fracturing for mask cost reduction2015 52nd ACM/EDAC/IEEE Design Automation Conference (DAC)
T. Chan, Puneet Gupta, Kwangsoo Han, A. Kagalwalla, A. Kahng (2014)
Benchmarking of Mask Fracturing HeuristicsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 36
Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations
D. FRANZBLAUf
PERFORMANCE GUARANTEES ON A SWEEP-LINE HEURISTIC FOR COVERING RECTILINEAR POLYGONS WITH RECTANGLES *
In the rectilinear picture compression problem we aim at selecting a minimum number of rectangular submatrices of a binary matrix M∈{0,1}m×n\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$M\in \{0,1\}^{m\times n}$$\end{document}, such that (a) every submatrix is composed entirely of ones, and (b) every 1-valued entry of M is present in some submatrix. This problem is motivated by the compression of monochromatic images, the synthesis of DNA arrays, the manufacture of integrated circuits, and other additional applications that have been identified in the literature. In this work we study several integer programming formulations for this problem. To tackle large-sized matrices, we propose an integer-programming-based heuristic procedure, which is based on three simple ideas: we produce a set C of M of maximal rectangles composed entirely of ones, we group the 1-valued entries of M into a set of atomic rectangles R, and we compute an optimum cover of R using only rectangles of C. We test this procedure on real image data from publicly available datasets, where we observe that image resolutions up to 1024×1024\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$1024 \times 1024$$\end{document} are processed within a few seconds. We also resort to CCITT instances used in previous works with known optima, and find for these instances a solution within 0.05%\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$0.05\%$$\end{document} of the optimum, outperforming the heuristic given by Litan et al.
4OR – Springer Journals
Published: Jun 1, 2023
Keywords: Integer programming; Rectilinear picture compression problem; Compression of monochromatic images; Heuristics; 90C10; 90C59
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.