The UGC Hardness Threshold of the L^sub p^ Grothendieck Problem

摘要

For p ≥ 2, the authors consider the problem of, given an n x n matrix A = (aij) whose diagonal entries vanish, approximating in polynomial time the number. When p = 2 this is simply the problem of computing the maximum eigenvalue of A, whereas for p = ∞ it is the Grothendieck problem on the complete graph, which was shown to have a O log n approximation algorithm in Nemirovski et al. The authors design a polynomial time algorithm which, given p ≥ 2 and an n x n matrix A = (aij) 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) they show that it is NP-hard to approximate Opt p (A) up to a factor smaller than p/e +1/4. Hence as p [arrow right] ∞ the UGC-hardness threshold for computing Opt p (A) is exactly (p/e) 1+o(1)). Show less