05822748

j

05822748 Coja-Oghlan, Amin Cooper, Colin Frieze, Alan An efficient sparse regularity concept. SIAM J. Discrete Math. 23, No. 4, 2000-2034 (2009). 2009 Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA EN approximation algorithms regularity Lemma matrix decomposition cut norm random discrete structures Zbl 0933.68061

doi:10.1137/080730160

Summary: Let ${A}$ be a $0/1$ matrix of size $m\times n$, and let $p$ be the density of ${A}$ (i.e., the number of ones divided by $m\cdot n$). We show that ${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 ${A}$, provided that ${A}$ satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of {\it A. M. Frieze} and {\it R. Kannan} [Combinatorica 19, No. 2, 175 -- 220 (1999; Zbl 0933.68061)] to sparse matrices. As an application, we obtain efficient $1-\varepsilon$ approximation algorithms for "bounded" instances of MAX CSP problems.