Name
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.
|
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/080730160 | SODA: Symposium on Discrete Algorithms |
Keywords | DocType | Volume |
efficient sparse regularity concept,times n,certain boundedness condition,cdot n,approximation algorithm,size m,cut matrix,max csp problem,cdot mnp,polynomial time,cut norm | Journal | 23 |
Issue | ISSN | ISBN |
4 | 0895-4801 | 978-0-89871-698-6 |
Citations | PageRank | References |
11 | 0.54 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| Colin Cooper | 2 | 857 | 91.88 |
| Alan M. Frieze | 3 | 4837 | 787.00 |