An efficient regularity concept for sparse graphs and matrices

Amin Coja-Oghlan, Colin Cooper, Alan Frieze

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 ε · 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. The decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan (Combinatorica 1999) to sparse matrices. As an application, we obtain efficient 1 - ε approximation algorithms for "bounded" instances of Max CSP problems.20
Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms
Pages2017-216
Number of pages10
Publication statusPublished - 2009

Keywords

  • approximation algorithms

Fingerprint

Dive into the research topics of 'An efficient regularity concept for sparse graphs and matrices'. Together they form a unique fingerprint.

Cite this