The Library
An efficient sparse regularity concept
Tools
Tools
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
