Approximating the cut-norm via Grothendieck's inequality

The cut-norm parallel to A parallel to(C) of a real matrix A = (a(ij)) (i is an element of R,j is an element of S) is the maximum, over all I subset of R, J subset of S, of the quantity \ Sigma(i is an element of I,j is an element of J)a(ij)\. 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 we provide an efficient approximation algorithm. This algorithm finds, for a given matrix A = (a(ij))(i is an element of R,j is an element of S), two subsets I subset of R and J subset of S, such that \ Sigma(i is an element of I,j is an element of J) a(ij)\ >= rho parallel to A parallel to(C), where rho > 0 is an absolute constant satisfying rho > 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 modi. cations which emphasize their algorithmic aspects. These proofs contain rounding techniques which go beyond the random hyperplane rounding of Goemans and Williamson [J. ACM, 42 (1995), pp. 1115-1145], allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case.