Approximating the cut-norm via Grothendieck's inequality

ABSTRACT

The cut-norm ||A||C of a real matrix A=(aij)i∈ R,j∈S is the maximum, over all I ⊂ R, J ⊂ S of the quantity | Σi ∈ I, j ∈ J aij|. This concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. Here we show that the problem of approximating the cut-norm of a given real matrix is MAX SNP hard, and provide an efficient approximation algorithm. This algorithm finds, for a given matrix A=(aij)i ∈ R, j ∈ S, two subsets I ⊂ R and J ⊂ S, such that | Σi ∈ I, j ∈ J aij| ≥ ρ ||A||C, where ρ > 0 is an absolute constant satisfying $ρ > 0. 56. The algorithm combines semidefinite programming with a rounding technique based on Grothendieck's Inequality. We present three known proofs of Grothendieck's inequality, with the necessary modifications which emphasize their algorithmic aspects. These proofs contain rounding techniques which go beyond the random hyperplane rounding of Goemans and Williamson [12], allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case.

REFERENCES

• 1: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 2: Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSP problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509945]
• 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 , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 5: N. Alon and J. Spencer, The Probabilistic Method, Second Edition, Wiley, New York, 2000.
• 6: S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and intractability of approximation problems, Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, 1992, 14--23.
• 7: J. Diestel, H. Jarchow and A. Tonge, Absolutely Summing Operators, Cambridge University Press, Cambridge, 1995.
• 8: A. M. Frieze and R. Kannan, Quick Approximation to matrices and applications, Combinatorica 19 (2) (1999) pp 175--200.
• 9: Uriel Feige , Michael Langberg, The RPR2 Rounding Technique for Semidefinite Programs, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.213-224, July 08-12, 2001
• 10: M. Grotschel, L. Lovasz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169--197.
• 11: A. Grothendieck, Resume de la theorie metrique des produits tensoriels topologiques, Bol. Soc. Mat. Sao Paulo 8 (1953), 1--79.
• 12: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 13: U. Haagerup, A new upper bound for the complex Grothendieck constant, Israel J. Math. 60 (1987), 199--224.
• 14: 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]
• 15: G. J. O. Jameson, Summing and nuclear norms in Banach space theory, London Mathematical Society Student Texts, 8, Cambridge University Press, Cambridge, 1987.
• 16: W. B. Johnson and J. Lindenstrauss, Basic concepts in the geometry of Banach spaces, Handbook of the geometry of Banach spaces, Vol. I, 1--84, North-Holland, Amsterdam, 2001.
• 17: H. Konig, On the complex Grothendieck constant in the n-dimensional case, London Math. Soc. Lect. Notes 158 (1990), 181--198.
• 18: J. L. Krivine, Sur la constante de Grothendieck, C. R. Acad. Sci. Paris Ser. A-B 284 (1977), 445--446.
• 19: Michael Lewin , Dror Livnat , Uri Zwick, Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.67-82, May 27-29, 2002
• 20: J. Lindenstrauss and A. Pelczynski, Absolutely summing operators in Lp-spaces and their applications, Studia Math. 29 (1968), 275--326.
• 21: Sanjeev Mahajan , H. Ramesh, Derandomizing Approximation Algorithms Based on Semidefinite Programming, SIAM Journal on Computing, v.28 n.5, p.1641-1663, April/May 1999 [doi>10.1137/S0097539796309326]
• 22: Y. E. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization, Optimization Methods and Software 9 (1998), 141--160.
• 23: C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comp. Sys. Sci. 43 (1991), 425--440.
• 24: R. E. Rietz, A proof of the Grothendieck inequality, Israel J. Math. 19 (1974), 271--276.
• 25: E. Szemeredi, Regular partitions of graphs, in: Proc. Colloque Inter. CNRS (J. -C. Bermond, J. -C. Fournier, M. Las Vergnas and D. Sotteau eds. ), 1978, 399-401.
• 26: A. Tanay, R. Sharan, M. Kupiec and R. Shamir, Revealing Modularity and Organization in the Yeast Molecular Network by Integrated Analysis of Highly Heterogeneous Genome-Wide Data, Proceedings of the National Academy of Sciences USA, 101 (2004), 2981--2986.
• 27: A. Tanay, R. Sharan and R. Shamir, Discovering Statistically Significant Biclusters in Gene Expression Data, Bioinformatics 18 (1) (2002), 136--144.
• 28: Uri Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.679-687, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301431]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

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

General Terms:
Algorithms, Theory

Keywords:
Grothendieck's inequaity, cut-norm, rounding techniques