Algorithms with large domination ratio

Noga Alon, Gregory Gutin, Michael Krivelevich

Research output: Contribution to journalArticlepeer-review

42 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)118-131
Number of pages14
JournalJournal of Algorithms
Issue number1
StatePublished - Jan 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


  • Approximation algorithms
  • Combinatorial optimization
  • Domination analysis


Dive into the research topics of 'Algorithms with large domination ratio'. Together they form a unique fingerprint.

Cite this