Matrix rounding with low error in small submatrices

Benjamin Doerr

Matrix rounding with low error in small submatrices

Benjamin Doerr

Christian-Albrechts-University Kiel

Résultats de recherche: Contribution à une conférence › Papier › Revue par des pairs

1 Citation (Scopus)

Résumé

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).

langue originale	Anglais
Pages	1067-1068
Nombre de pages	2
état	Publié - 1 juil. 2005
Modification externe	Oui
Evénement	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, États-Unis Durée: 23 janv. 2005 → 25 janv. 2005

Une conférence

Une conférence	Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pays/Territoire	États-Unis
La ville	Vancouver, BC
période	23/01/05 → 25/01/05

Contient cette citation

@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

Résumé

Une conférence

Empreinte digitale

Contient cette citation