AN EFFICIENT SPARSE REGULARITY CONCEPT

作者：Coja Oghlan Amin^*; Cooper Colin; Frieze Alan

来源：SIAM Journal on Discrete Mathematics, 2010, 23(4): 2000-2034.

DOI：10.1137/080730160

• approximation algorithms
• regularity lemma
• matrix decomposition
• cut norm
• random discrete structures

Let A be a 0/1 matrix of size m x 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 epsilon . 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 - epsilon approximation algorithms for "bounded" instances of MAX CSP problems.

• 出版日期2010