Let $P$ be an optimization problem, and let $A$ be an approximation algorithm for $P$. The domination ratio $\domr(A,n)$ is the maximum real $q$ such that the solution $x(I)$ obtained by $A$ for any instance $I$ of $P$ of size $n$ is not worse than at least a fraction $q$ of the feasible solutions of $I$. We describe a deterministic, polynomial time algorithm with domination ratio $1-o(1)$ for the partition problem, and a deterministic, polynomial time algorithm with domination ratio $\Omega(1)$ for the MaxCut problem and for some far-reaching extensions of it, including Max-$r$-Sat, for each fixed $r$. The techniques combine combinatorial and probabilistic methods with tools from Harmonic Analysis.
Citation
Tech. Report Dept of Computer Science Royal Holloway, University of London 03-04