
The Library
An efficient sparse regularity concept
Tools
Coja-Oghlan, Amin, Cooper, Colin and Frieze, Alan (2010) An efficient sparse regularity concept. SIAM Journal on Discrete Mathematics, Volume 23 (Number 4). pp. 2000-2034. doi:10.1137/080730160 ISSN 0895-4801.
|
PDF
WRAP_Coja-Oghlan_sparsreg.pdf - Published Version - Requires a PDF viewer. Download (603Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/080730160
Abstract
Let A be a 0/1 matrix of size m×n, and let p be the density of A (i.e., the number of ones divided by m · n). We show that A can be approximated in the cut norm within ε · mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m · n of A, provided that A satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan [Combinatorica, 19 (1999), pp. 175–220] to sparse matrices. As an application, we obtain efficient 1−ε approximation algorithms for "bounded" instances of MAX CSP problems.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Approximation theory, Decomposition (Mathematics), Matrices | ||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0895-4801 | ||||
Official Date: | 6 January 2010 | ||||
Dates: |
|
||||
Volume: | Volume 23 | ||||
Number: | Number 4 | ||||
Page Range: | pp. 2000-2034 | ||||
DOI: | 10.1137/080730160 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 20 December 2015 | ||||
Date of first compliant Open Access: | 20 December 2015 | ||||
Funder: | Deutsche Forschungsgemeinschaft (DFG), Royal Society (Great Britain), National Science Foundation (U.S.) (NSF) | ||||
Grant number: | CO 646 (DFG), 2006/R2-IJP (RS), CCF0502793 (NSF) |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year