Algorithms with large domination ratio

Noga Alon, Gregory Gutin, Michael Krivelevich

Research output: Contribution to journalArticle

37 Scopus citations

Abstract

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
Volume50
Issue number1
DOIs
StatePublished - Jan 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Approximation algorithms
  • Combinatorial optimization
  • Domination analysis

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

  • Cite this