Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Doerr, Benjamin

dblp



BibTeX cite key*:

DoerrTusnady

Title

Title*:

Matrix approximation and Tusnády's problem

Journal

Journal Title*:

European Journal of Combinatorics

Journal's URL:


Download URL
for the article:

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6WDY-4J2KT3X-1-1&_cdi=6779&_user=43521&_orig=browse&_coverDate=04%2F30%2F2007&_sk=999719996&view=c&wchp=dGLbVlz-zSkWb&md5=7e761b57e411050e0c023a1692bbcbda&ie=/sdarticle.pdf

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0195-6698

Vol, No, pp, Date

Volume*:

28

Number:

3

Publishing Date:

2007

Pages*:

990-995

Number of
VG Pages:

18

Page Start:

990

Page End:

995

Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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 there is an integer matrix such that

holds for all intervals I[m], J[n]. Such a matrix can be computed in time O(mnlog(min{m,n})). The result remains true if we add the requirement |aij−bij|<2 for all i[m],j[n]. This is surprising.

URL for the Abstract:

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WDY-4J2KT3X-1&_user=43521&_coverDate=04%2F30%2F2007&_rdoc=29&_fmt=summary&_orig=browse&_srch=doc-info(%23toc%236779%232007%23999719996%23638422%23FLA%23display%23Volume)&_cdi=6779&_sort=d&_docanchor=&view=c&_ct=31&_acct=C000004638&_version=1&_urlVersion=0&_userid=43521&md5=90e8659ca14408a66494b505d85b1a67

Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{DoerrTusnady,
AUTHOR = {Doerr, Benjamin},
TITLE = {Matrix approximation and {Tusn{\'a}dy's} problem},
JOURNAL = {European Journal of Combinatorics},
PUBLISHER = {Elsevier},
YEAR = {2007},
NUMBER = {3},
VOLUME = {28},
PAGES = {990--995},
ADDRESS = {Amsterdam, The Netherlands},
ISBN = {0195-6698},
}


Entry last modified by Benjamin Doerr, 05/05/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Mathias Bader
Created
03/09/2007 12:15:52 PM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Benjamin Doerr
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
05/05/2009 09:26:35 PM
08.02.2008 13:51:30
08.02.2008 13:51:00
08.02.2008 13:50:30
20.01.2008 10:14:51