Matrix rounding with low error in small submatrices

Benjamin Doerr

Matrix rounding with low error in small submatrices

Benjamin Doerr

Christian-Albrechts-University Kiel

Research output: Contribution to conference › Paper › peer-review

Abstract

We show that any real valued matrix A can be rounded to an integer one B such that the error in all 2 × 2 (geometric) submatrices is less than 1.5, that is, we have |a_ij - b_ij| < 1 and | Σ_k=iⁱ⁺¹ Σ_l=j^j+1 (a _kl - b_kl)| < 1.5 for all i, j. More precisely, an error of less than 1.5 - 3^-2mn + 3^-d+1 can be achieved in time O (mnd).

Original language	English
Pages	1067-1068
Number of pages	2
Publication status	Published - 1 Jul 2005
Externally published	Yes
Event	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: 23 Jan 2005 → 25 Jan 2005

Conference

Conference	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Vancouver, BC
Period	23/01/05 → 25/01/05

Cite this

@conference{f907bf240a2c43f0b7a92e13e1accdaf,

title = "Matrix rounding with low error in small submatrices",

abstract = "We show that any real valued matrix A can be rounded to an integer one B such that the error in all 2 × 2 (geometric) submatrices is less than 1.5, that is, we have |aij - bij| < 1 and | Σk=ii+1 Σl=jj+1 (a kl - bkl)| < 1.5 for all i, j. More precisely, an error of less than 1.5 - 3-2mn + 3-d+1 can be achieved in time O (mnd).",

author = "Benjamin Doerr",

year = "2005",

month = jul,

day = "1",

language = "English",

pages = "1067--1068",

note = "Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 23-01-2005 Through 25-01-2005",

}

TY - CONF

T1 - Matrix rounding with low error in small submatrices

AU - Doerr, Benjamin

PY - 2005/7/1

Y1 - 2005/7/1

N2 - We show that any real valued matrix A can be rounded to an integer one B such that the error in all 2 × 2 (geometric) submatrices is less than 1.5, that is, we have |aij - bij| < 1 and | Σk=ii+1 Σl=jj+1 (a kl - bkl)| < 1.5 for all i, j. More precisely, an error of less than 1.5 - 3-2mn + 3-d+1 can be achieved in time O (mnd).

AB - We show that any real valued matrix A can be rounded to an integer one B such that the error in all 2 × 2 (geometric) submatrices is less than 1.5, that is, we have |aij - bij| < 1 and | Σk=ii+1 Σl=jj+1 (a kl - bkl)| < 1.5 for all i, j. More precisely, an error of less than 1.5 - 3-2mn + 3-d+1 can be achieved in time O (mnd).

M3 - Paper

AN - SCOPUS:20744449460

SP - 1067

EP - 1068

T2 - Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 23 January 2005 through 25 January 2005

ER -

Matrix rounding with low error in small submatrices

Abstract

Conference

Fingerprint

Cite this