Alon, N., Gutin, Gregory and Krivelevich, M. (2004) Algorithms with large domination ratio. Journal of Algorithms, 50 (1).
Full text access: Open
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 Ω(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.
This is a Submitted version This version's date is: 2004 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/5f5dc7b8-bb49-d01d-e313-6a1297fa0276/7/
Deposited by Research Information System (atira) on 22-Jul-2014 in Royal Holloway Research Online.Last modified on 22-Jul-2014