### 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 language | English (US) |
---|---|

Pages (from-to) | 118-131 |

Number of pages | 14 |

Journal | Journal of Algorithms |

Volume | 50 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2004 |

Externally published | Yes |

### 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

*Journal of Algorithms*,

*50*(1), 118-131. https://doi.org/10.1016/j.jalgor.2003.09.003