Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:An efficient regularity concept for sparse graphs and matrices
Authors: Amin Coja-Oghlan ; Colin Cooper ; Alan Frieze
Date:Mar 2008
Publication Type:Conference Paper Publication Status:Pre-print
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
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 = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh