DIMACS TR: 2002-01

A Trade-Off for Covering the Off-Diagonal Elements of Matrices

Authors: Vince Grolmusz


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