%0 Conference Paper %1 kindler08 %A Kindler, Guy %A Naor, Assaf %A Schechtman, Gideon %B SODA %D 2008 %E Teng, Shang-Hua %I SIAM %K complexity np-hardness spin.glass unique.game.conjecture %P 64--73 %R 10.1145/1347082.1347090 %T The UGC Hardness Threshold of the $\ell_p$ Grothendieck Problem %X For p ≥ 2 we consider the problem of, given an n × n matrix A = (aij) whose diagonal entries vanish, approximating in polynomial time the number display equation (where optimization is taken over real numbers). When p = 2 this is simply the problem of computing the maximum eigenvalue of A, while for p = ∞ (actually it suffices to take p ≈ log n) it is the Grothendieck problem on the complete graph, which was shown to have a O(log n) approximation algorithm in 27, 26, 15, and was used in 15 to design the best known algorithm for the problem of computing the maximum correlation in Correlation Clustering. Thus the problem of approximating Optp (A) interpolates between the spectral (p = 2) case and the Correlation Clustering (p = ∞) case. From a physics point of view this problem corresponds to computing the ground states of spin glasses in a hard-wall potential well. We design a polynomial time algorithm which, given p ≥ 2 and an n x n matrix A = (aij) with zeros on the diagonal, computes Optp (A) up to a factor p/e + 30 log p. On the other hand, assuming the unique games conjecture (UGC) we show that it is NP-hard to approximate (1.2) up to a factor smaller than p/e + 1/4. Hence as p → ∞ the UGC-hardness threshold for computing Optp (A) is exactly p/e (1 + o(1)).

@inproceedings{kindler08, abstract = {For p ≥ 2 we consider the problem of, given an n × n matrix A = (aij) whose diagonal entries vanish, approximating in polynomial time the number {display equation} (where optimization is taken over real numbers). When p = 2 this is simply the problem of computing the maximum eigenvalue of A, while for p = ∞ (actually it suffices to take p ≈ log n) it is the Grothendieck problem on the complete graph, which was shown to have a O(log n) approximation algorithm in [27, 26, 15], and was used in [15] to design the best known algorithm for the problem of computing the maximum correlation in Correlation Clustering. Thus the problem of approximating Optp (A) interpolates between the spectral (p = 2) case and the Correlation Clustering (p = ∞) case. From a physics point of view this problem corresponds to computing the ground states of spin glasses in a hard-wall potential well. We design a polynomial time algorithm which, given p ≥ 2 and an n x n matrix A = (aij) with zeros on the diagonal, computes Optp (A) up to a factor p/e + 30 log p. On the other hand, assuming the unique games conjecture (UGC) we show that it is NP-hard to approximate (1.2) up to a factor smaller than p/e + 1/4. Hence as p → ∞ the UGC-hardness threshold for computing Optp (A) is exactly p/e (1 + o(1)).}, added-at = {2011-01-18T22:09:08.000+0100}, author = {Kindler, Guy and Naor, Assaf and Schechtman, Gideon}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/2134245f2fcf1ad1b59d0b3ca5f24a97c/ytyoun}, booktitle = {SODA}, crossref = {DBLP:conf/soda/2008}, doi = {10.1145/1347082.1347090}, editor = {Teng, Shang-Hua}, interhash = {d7c2b197b9b542e9baf348f5ba907c50}, intrahash = {134245f2fcf1ad1b59d0b3ca5f24a97c}, keywords = {complexity np-hardness spin.glass unique.game.conjecture}, pages = {64--73}, publisher = {SIAM}, timestamp = {2016-11-13T11:08:09.000+0100}, title = {The {UGC} Hardness Threshold of the $\ell_p$ {Grothendieck} Problem}, year = 2008 }