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

Preview

PDF WRAP_Coja-Oghlan_sparsreg.pdf - Published Version - Requires a PDF viewer. Download (603Kb) | Preview

Request Changes to record.

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:	Date Event 6 January 2010 Published
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
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