Benjamin Doerr:

Matrix Approximation and Tusnády's Problem

We consider the problem of approximating a given matrix by an integer one such that in all geometric submatrices the sum of the entries does not change by much. We show that for all integers m, n ≥ 2 and real matrices A ∈ R^{m x n} there is an integer matrix B ∈ Z^{m x n} such that

holds for all intervals I ⊆ [m], J ⊆ [n]. Such a matrix can be computed in time O(m n log(min{m,n})). The result remains true, if we add the requirement

for all i ∈ [m], j ∈ [n]. This is surprising, as the slightly stronger requirement ¦ a_ij - b_ij ¦ < 1 makes the problem equivalent to Tusnády's problem.

Mathematics Subject Classification (1991): 11K38

Keywords: Rounding, integral approximation, discrepancy

Mail an Jens Burmeister

[Thu Feb 19 18:56:36 2009]

Impressum