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.