TY - JOUR

T1 - Algorithms with large domination ratio

AU - Alon, Noga

AU - Gutin, Gregory

AU - Krivelevich, Michael

N1 - Funding Information:
* Corresponding author. E-mail addresses: nogaa@post.tau.ac.il (N. Alon), gutin@cs.rhul.ac.uk (G. Gutin), krivelev@post.tau.ac.il (M. Krivelevich). 1 Research supported in part by a USA–Israeli BSF grant and by a grant from the Israel Science Foundation. 2 Research supported in part by a USA–Israel BSF Grant, by a grant from the Israel Science Foundation, and by a Bergmann Memorial Grant.

PY - 2004/1

Y1 - 2004/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Combinatorial optimization

KW - Domination analysis

UR - http://www.scopus.com/inward/record.url?scp=0346640462&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346640462&partnerID=8YFLogxK

U2 - 10.1016/j.jalgor.2003.09.003

DO - 10.1016/j.jalgor.2003.09.003

M3 - Article

AN - SCOPUS:0346640462

VL - 50

SP - 118

EP - 131

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 1

ER -