TY - GEN
T1 - The UGC hardness threshold of the l p Grothendieck problem
AU - Kindler, Guy
AU - Naor, Assaf
AU - Schechtman, Gideon
PY - 2008
Y1 - 2008
N2 - For p ≥ 2 we consider the problem of, given an n × n matrix A = (a ij) whose diagonal entries vanish, approximating in polynomial time the number Opt p(A):= max{Σ n i,j=1a ijx ix j: (Σ n i=1|x i| p) 1/P ≤1} (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 Opt p(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 × n matrix A = (a ij) with zeros on the diagonal, computes Opt p(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 Opt p(A) is exactly p/e (1 + o(1)).
AB - For p ≥ 2 we consider the problem of, given an n × n matrix A = (a ij) whose diagonal entries vanish, approximating in polynomial time the number Opt p(A):= max{Σ n i,j=1a ijx ix j: (Σ n i=1|x i| p) 1/P ≤1} (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 Opt p(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 × n matrix A = (a ij) with zeros on the diagonal, computes Opt p(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 Opt p(A) is exactly p/e (1 + o(1)).
UR - http://www.scopus.com/inward/record.url?scp=58449126386&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58449126386&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:58449126386
SN - 9780898716474
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 64
EP - 73
BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 20 January 2008 through 22 January 2008
ER -