The UGC Hardness Threshold of the Lp Grothendieck Problem

• 成果类型: Article
• 署名作者: Kindler, Guy; Naor, Assaf; Schechtman, Gideon
• 署名单位: Hebrew University of Jerusalem; New York University; Weizmann Institute of Science
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1090.0425
• 发表日期: 2010
• 页码: 267-283
• 关键词: spin-glass; complexity; cut

摘要

For p >= 2 we consider the problem of, given an n x n matrix A = (a(ij)) whose diagonal entries vanish, approximating in polynomial time the number Opt(p)(A):= max{(i,j=1)Sigma(n) a(ij)x(i)x(j): (x(1), ..., x(n)) is an element of R-n boolean AND ((i=1)Sigma(n) vertical bar x(i)vertical bar(p))(1/p) <= 1}. When p = 2 this is simply the problem of computing the maximum eigenvalue of A, whereas for p = infinity ( actually it suffices to take p approximate to log n) it is the Grothendieck problem on the complete graph, which was shown to have a O(log n) approximation algorithm in Nemirovski et al. [Nemirovski, A., C. Roos, T. Terlaky. 1999. On maximization of quadratic form over intersection of ellipsoids with common center. Math. Program. Ser. A 86(3) 463-473], Megretski [Megretski, A. 2001. Relaxations of quadratic programs in operator theory and system analysis. Systems, Approximation, Singular Integral Operators, and Related Topics (Bordeaux, 2000), Vol. 129. Operator Theory Advances and Applications. Birkhauser, Basel, 365-392], Charikar and Wirth [Charikar, M., A. Wirth. 2004. Maximizing quadratic programs: Extending Grothendieck's inequality. Proc. 45th Annual Sympos. Foundations Comput. Sci., IEEE Computer Society, 54-60] and was used in the work of Charikar and Wirth noted above, 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=infinity) 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 = (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 Opt(p)(A) up to a factor smaller than p/e + 1/4. Hence as p -> infinity the UGC-hardness threshold for computing Opt(p)(A) is exactly (p/e)(1 + o(1)).