Approximating integer quadratic programs and MAXCUT in subdense graphs
Let A be a real symmetric n x n-matrix with eigenvalues, lambda(1),..., lambda(n) ordered after decreasing absolute value, and b an n x 1-vector. We present an algorithm finding approximate solutions to min x*(Ax+b) and maxx*(Ax+b) over x is an element of {-1,1}(n), with an absolute error of at most (c(1) vertical bar lambda(1)vertical bar +vertical bar lambda([c2 log n])vertical bar)2n + O(alpha