DIMACS TR: 2002-01
A Trade-Off for Covering the Off-Diagonal Elements of Matrices
Authors: Vince Grolmusz
ABSTRACT
We would like to cover all the off-diagonal elements of an $n\times n$
matrix by non-necessarily contiguous rectangular submatrices; the
diagonal elements cannot be covered. It is not difficult to give a cover
with $2\lceil \log n\rceil$ rectangles, where some off-diagonal elements
are covered as many as $\lceil \log n\rceil$-times, or another cover,
using $n$ rectangles and any off-diagonal elements of the matrix is
covered only once. We show that one cannot attain {\it both} low
covering multiplicity and a small number of covering rectangles at the
same time: We prove a trade-off between these two numbers.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-01.ps.gz
DIMACS Home Page