English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. Search Results / 
  2. View item

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
 PreviousNext  
  Matrix Approximation and Tusnády’s Problem

Doerr, B. (2007). Matrix Approximation and Tusnády’s Problem. European Journal of Combinatorics, 28(3), 990-995.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1FCD-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0029-BD43-3
Genre: Journal Article

Files

show Files
hide Files
:
DoerrTusnady.pdf (Publisher version), 5KB
 
File Permalink:
-
Name:
DoerrTusnady.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Doerr, Benjamin1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2008-02-282007
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 356706
Other: Local-ID: C12573CC004A8E26-83C541C6FDCEE445C1257299003DE0E6-DoerrTusnady
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: European Journal of Combinatorics
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: London : Academic Press
Pages: - Volume / Issue: 28 (3) Sequence Number: - Start / End Page: 990 - 995 Identifier: ISSN: 0195-6698
CoNE: https://pure.mpg.de/cone/journals/resource/954922648096