- 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 eps*mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size mn of A, provided that A satisfies a certain boundedness condition. This condition basically says that A does not feature any large, very dense spots. Moreover, the decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan (1999) to sparse matrices. As an application, we obtain efficient 1-eps approximation algorithms for problems such as MAX CUT and MAX k-SAT on ``bounded'' problem instances.
- Links To Paper
- 1st Link
- Bibtex format
- @InProceedings{EDI-INF-RR-1239,
- author = {
Amin Coja-Oghlan
and Colin Cooper
and Alan Frieze
},
- title = {An efficient regularity concept for sparse graphs and matrices},
- book title = {},
- year = 2008,
- month = {Mar},
- url = {http://web.mac.com/aminco/xmatrix2.pdf},
- }
|
