An Efficient Sparse Regularity Concept
Amin Coja‐Oghlan, Colin Cooper, ALAN M. FRIEZE · SIAM Journal on Discrete Mathematics · 2010
Let ${\bf A}$ be a $0/1$ matrix of size $m\times n$, and let p be the density of ${\bf A}$ (i.e., the number of ones divided by $m\cdot n$). We show that ${\bf A}$ can be approximated in the cut norm within $\varepsilon\cdot mnp$ by a sum of cut matrices (of rank 1), where the number of summands is independent of the size $m\cdot n$ of ${\bf A}$, provided that ${\bf 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-\varepsilon$ approximation algorithms for “bounded” instances of MAX CSP problems.