Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs

Abstract

Let A be a real symmetric n× n-matrix with eigenvalues λ ₁,⋯,λ _n ordered after decreasing absolute value, and b an n× 1-vector. We present an algorithm finding approximate solutions to min x*(Ax + b) and max x*(Ax + b) over x∈ {–1,1}ⁿ, with an absolute error of at most $(c_{1}|{\rm \lambda_{1}}|+|{\rm \lambda}_{\lceil c_{2} {\rm log}n\rceil}|)2n+O((\alpha n+\beta)\sqrt{n {\rm log}n})$, where α and β are the largest absolute values of the entries in A and b, respectively, for any positive constants c ₁ and c ₂, in time polynomial in n.

We demonstrate that the algorithm yields a PTAS for MAXCUT in regular graphs on n vertices of degree d of $\omega(\sqrt{n{\rm log}n})$, as long as they contain O(d ⁴log n) 4-cycles. The strongest previous result showed that Ω(n/log n) average degree graphs admit a PTAS.

We also show that smooth n-variate polynomial integer programs of constant degree k, always can be approximated in polynomial time leaving an absolute error of o(n ^k), answering in the affirmative a suspicion of Arora, Karger, and Karpinski in STOC 1995.