research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleApproximating almost all instances of Max-Cut within a ratio above the Hastad threshold
Bibtex cite IDRACTI-RU1-2006-65
Booktitle 14th Annual European Symposium on Algorithms (ESA 2006)
Series Lecture Notes in Computer Science
Year published 2006
Month September
Volume 4168
Pages 432-443
Publisher Springer, L.N Computer Science
Note international
DOI 10.1007/11841036_40
We give a deterministic polynomial-time algorithm which for any given average degree d and asymptotically almost all random graphs G in G(n, m = [d/2 n]) outputs a cut of G whose ratio (in cardinality) with the maximum cut is at least 0.952. We remind the reader that it is known that unless P=NP, for no constant å>0 is there a Max-Cut approximation algorithm that for all inputs achieves an approximation ratio of (16/17) +å (16/17 < 0.94118).
Kaporis, Alexis
Kirousis, Lefteris
Stavropoulos, Elias
fulltext.pdf (main file)
Publication ID201