Let A be a real symmetric n x n-matrix with eigenvalues λ_i, • • •, λ_n ordered after decreasing absolute value, and 6 an n x -vector. We present an algorithm finding approximate solutions to min x~*(Ax+b) and max x~*(Ax + b) over x ∈ {— 1, 1}~n, with an absolute error of at most (c_1|λ_1 + |λ_([c_2 log n])|)2n + O((αn + β)((n log n)~(1/2)), where α and β are the largest absolute values of the entries in A and b, respectively, for any positive constants c_1 and c_2, 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 ω((n log n)~(1/2)), as long as they contain O(d~4 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.
展开▼
