An efficient sparse regularity concept

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.

REFERENCES

• 1: N. Alon, A. Coja-Oghlan, H. Han, M. Kang, V. Rödl, M. Schacht: Quasi-randomness and algorithmic regularity for graphs with general degree distributions. Proc. 34th ICALP (2007) 789--800
• 2: Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSPs, Journal of Computer and System Sciences, v.67 n.2, p.212-243, September 2003 [doi>10.1016/S0022-0000(03)00008-4]
• 3: N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
• 4: Noga Alon , Assaf Naor, Approximating the cut-norm via Grothendieck's inequality, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007371]
• 5: Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP -hard problems, Journal of Computer and System Sciences, v.58 n.1, p.193-210, Feb. 1999 [doi>10.1006/jcss.1998.1605]
• 6: Ravi B. Boppana, Eigenvalues and graph bisection: An average-case analysis, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, p.280-285, October 12-14, 1987 [doi>10.1109/SFCS.1987.22]
• 7: Amin Coja-Oghlan, A spectral heuristic for bisecting random graphs, Random Structures & Algorithms, v.29 n.3, p.351-398, October 2006 [doi>10.1002/rsa.v29:3]
• 8: Amin Coja-oghlan , Andreas Goerdt , André Lanka, Strong Refutation Heuristics for Random k-SAT, Combinatorics, Probability and Computing, v.16 n.1, p.5-28, January 2007 [doi>10.1017/S096354830600784X]
• 9: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 10: Uriel Feige , Jeong Han Kim , Eran Ofek, Witnesses for non-satisfiability of dense random 3CNF formulas, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.497-508, October 21-24, 2006 [doi>10.1109/FOCS.2006.78]
• 11: W. Fernandez de la Vega, MAX-CUT has a randomized approximation scheme in dense graphs, Random Structures & Algorithms, v.8 n.3, p.187-198, May 1996 [doi>10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U]
• 12: W. Fernandez de la Vega , Marek Karpinski , Ravi Kannan , Santosh Vempala, Tensor decomposition and approximation schemes for constraint satisfaction problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060701]
• 13: Joel Friedman , Andreas Goerdt , Michael Krivelevich, Recognizing More Unsatisfiable Random k-SAT Instances Efficiently, SIAM Journal on Computing, v.35 n.2, p.408-430, 2005 [doi>10.1137/S009753970444096X]
• 14: A. Frieze, R. Kannan: Quick approximation to matrices and applications. Combinatorica 19 (1999) 175--220
• 15: S. Gerke, A. Steger: The sparse regularity lemma and its applications In: B. Webb (ed.): Surveys in combinatorics. Cambridge University Press (2005) 227--258
• 16: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 17: T. Gowers: Lower bounds of tower type for Szemerédi's uniformity lemma. Geometric and Functional Analysis 7 (1997) 322--337
• 18: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 19: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 20: Y. Kohayakawa, Szemerédi's regularity lemma for sparse graphs, Selected papers of a conference on Foundations of computational mathematics, p.216-230, September 1997, Rio de Janeiro, Brazil
• 21: V. Rödl: unpublished.
• 22: E. Szemerédi: Regular partitions of graphs, Problémes Combinatoires et Théorie des Graphes Colloques Internationaux CNRS 260 (1978) 399--401
• 23: Luca Trevisan , Gregory B. Sorkin , Madhu Sudan , David P. Williamson, Gadgets, Approximation, and Linear Programming, SIAM Journal on Computing, v.29 n.6, p.2074-2097, April 2000 [doi>10.1137/S0097539797328847]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms