Algorithms with large domination ratio

Noga Alon; Gregory Gutin; Michael Krivelevich

doi:10.1016/j.jalgor.2003.09.003

Algorithms with large domination ratio

Noga Alon, Gregory Gutin, Michael Krivelevich

Research output: Contribution to journal › Article › peer-review

43 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 language	English (US)
Pages (from-to)	118-131
Number of pages	14
Journal	Journal of Algorithms
Volume	50
Issue number	1
DOIs	https://doi.org/10.1016/j.jalgor.2003.09.003
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

Access to Document

10.1016/j.jalgor.2003.09.003

Cite this

@article{d5e298df914b49baa82ebb2ce319b154,

title = "Algorithms with large domination ratio",

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.",

keywords = "Approximation algorithms, Combinatorial optimization, Domination analysis",

author = "Noga Alon and Gregory Gutin and Michael Krivelevich",

note = "Funding Information: * Corresponding author. E-mail addresses: [email protected] (N. Alon), [email protected] (G. Gutin), [email protected] (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.",

year = "2004",

month = jan,

doi = "10.1016/j.jalgor.2003.09.003",

language = "English (US)",

volume = "50",

pages = "118--131",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

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: [email protected] (N. Alon), [email protected] (G. Gutin), [email protected] (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

SN - 0196-6774

VL - 50

SP - 118

EP - 131

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

Algorithms with large domination ratio

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this