Grothendieck-type inequalities in combinatorial optimization (Q2892967)

The Grothendieck inequality originated in [\textit{A.~Grothendieck}, ``Résumé de la théorie métrique des produits tensoriels topologiques'', Bol. Soc. Mat. São Paulo 8, 1--79 (1956; Zbl 0074.32303)] as his ``théorème fondamental de la théorie métrique des produits tensoriels''; technically it asserts the equivalence of the ``Hilbertian'' and the projective tensor norm on \(C(K)\otimes C(K)\). Only later was it reformulated as an inequality for matrices by \textit{J.~Lindenstrauss} and \textit{A.~Pełczyński} [``Absolutely summing operators in \({\mathcal L}_p\)-spaces and their applications'', Stud.\ Math.\ 29, 275--326 (1968; Zbl 0183.40501)] who gave ``the first proof of this theorem understandable for average mathematicians'', as A.~Pietsch put it (p.~138 in his ``Operator ideals''). In the last few years, the Grothendieck inequality has turned out to be of great importance in discrete mathematics, in particular in combinatorial optimisation and computational complexity. The very nice paper under review surveys these connections.NEWLINENEWLINEThe Grothendieck inequality reads as follows. There is a universal constant \(K_G\) such that whenever \((a_{ij})\) is a real \((m\times n)\)-matrix satisfying NEWLINE\[NEWLINE \sup \biggl\{ \Bigl| \sum_{i,j} a_{ij} s_i t_j \Bigr| : |s_i|, |t_j|\leq1 \biggr\} \leq 1 NEWLINE\]NEWLINE for scalars, \(s_i\), \(t_j\), then NEWLINE\[NEWLINE \sup \biggl\{ \Bigl| \sum_{i,j} a_{ij} \langle x_i, y_j \rangle \Bigr| : \|x_i\|, \|y_j\|\leq1 \biggr\} \leq K_G NEWLINE\]NEWLINE for vectors \(x_i\), \(y_j\) in a Hilbert space. The best possible choice of this constant is called the Grothendieck constant. Usually one considers square matrices, but by padding with zeros one might as well allow \(m\times n\)-matrices. Also, it is clear that it is enough to consider numbers of modulus~\(1\) and vectors of norm~\(1\), and \(m+n\) of them live in an \(m+n\)-dimensional Hilbert space, hence in the unit sphere \(S^{m+n-1}\) of \({\mathbb R}^{m+n}\). Thus, the Grothendieck inequality takes the form NEWLINE\[NEWLINE\begin{multlined} \max\biggl\{ \sum_{i,j} a_{ij} \langle x_i, y_j \rangle: \{x_i\}_{i=1}^m, \;\{y_j\}_{j=1}^n \subset S^{m+n-1} \biggr\} \leq \\K_G\;\max\biggl\{ \sum_{i,j} a_{ij} s_i t_j : \{s_i\}_{i=1}^m, \;\{t_j\}_{j=1}^n \subset \{\pm1\} \biggr\}. \end{multlined}\tag{1} NEWLINE\]NEWLINENEWLINENEWLINEThe key point is now that maximising the right hand side is a ``hard'' problem of integer programming, but maximising the left hand side is ``easy'' by what is called semidefinite programming; indeed there is a polynomial time algorithm that achieves this. Hence one can approximate the maximum on the right hand side in polynomial time, up to a factor~\(K_G\). Several instances of this idea are presented in Section 2 of the paper: estimation of the cut norm of a real matrix, Szemerédi partitions for graphs, Frieze-Kannan matrix decompositions, maximum acyclic subgraphs, linear equations modulo~\(2\). Further, the authors explain how these ideas are related to finding the best known estimate of \(K_G\), viz.\ \(K_G < \pi/(2\log(1+\sqrt{2}))\); for this one has to replace the vectors in (1) by numbers \(\pm1\), a process the authors call rounding. (For more on this see [\textit{M. Braverman, K. Makarychev, Yu. Makarychev} and \textit{A. Naor}, ``The Grothendieck constant is strictly smaller than Krivine's bound'', \url{arXiv:1103.61061}].)NEWLINENEWLINEIn Section 3, the Grothendieck constant of a graph is defined and studied; here (1) corresponds to the case of a bipartite graph. Algorithmic consequences for spin glasses and correlation clustering are presented. Further sections are devoted to kernel clustering and the propeller conjecture, \(L_p\)-type Grothendieck inequalities (in which the cube appearing on the right hand side of (1) is replaced by other convex bodies like the \(\ell_p^n\)-unit ball) and higher rank Grothendieck inequalities.NEWLINENEWLINEThe final section explains that for many problems that are shown to be tractable up to \(K_G\) by means of a Grothendieck type inequality, this is actually a threshold in that there is no polynomial time algorithm that calculates the quantity in question up to a smaller ratio. In fact, these are conditional results that rely on some assumption like the so-called unique games conjecture, a relative of \(\text{P} \neq \text{NP}\).NEWLINENEWLINEThis very well written survey should be read by everyone who is interested in applications of functional analysis to discrete mathematics. It is written with an audience in mind that does not consist of specialists in combinatorial optimisation. Being one of those nonspecialists I can safely say that the paper achieves its goal admirably and makes good reading.NEWLINENEWLINEFor another splendid survey on topics related to the Grothendieck inequality see [\textit{G. Pisier}, ``Grothendieck's theorem, past and present,'' Bull. Am. Math. Soc., New Ser. 49, No.~2, 237--323 (2012; Zbl 1244.46006)].