One-dimensional relaxations for the problem of covering a polygonal region by rectangles
Authors: G. Scheithauer
Preprint MATH-NM-04-2009, TU Dresden
The problem of covering a polygonal target set by a finite number of rectangles is a hard decision problem. The aim of the paper is to develop necessary conditions which have to be fulfilled by any covering. For that reason several one-dimensional relaxations are considered and cover-feasible functions are introduced.