# Matrix approximation and Tusnády’s problem

- Authors
- Journal
- European Journal of Combinatorics 0195-6698
- Publisher
- Elsevier
- Publication Date
- Volume
- 28
- Issue
- 3
- Identifiers
- DOI: 10.1016/j.ejc.2005.09.006
- Disciplines

## Abstract

Abstract 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 × n there is an integer matrix B ∈ Z m × n such that | ∑ i ∈ I ∑ j ∈ J ( a i j − b i j ) | < 4 log 2 ( min { m , n } ) 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 | a i j − b i j | < 2 for all i ∈ [ m ] , j ∈ [ n ] . This is surprising, as the slightly stronger requirement | a i j − b i j | < 1 makes the problem equivalent to Tusnády’s problem.

## There are no comments yet on this publication. Be the first to share your thoughts.