Back to Search
Start Over
AN EFFICIENT SPARSE REGULARITY CONCEPT.
- Source :
-
SIAM Journal on Discrete Mathematics . 2009, Vol. 23 Issue 4, p2000-2034. 35p. - Publication Year :
- 2009
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 23
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 51789526
- Full Text :
- https://doi.org/10.1137/080730160