@inproceedings{ed79759dced8463191c270377c0ecdaa,
title = "Approximating almost all instances of MAX-CUT within a ratio above the h{\aa}stad threshold",
abstract = "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/2n]) 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 e > 0 is there a MAX-CUT approximation algorithm that for all inputs achieves an approximation ratio of (16/17) + ε (16/17 < 0.94118).",
author = "Kaporis, {A. C.} and Kirousis, {L. M.} and Stavropoulos, {E. C.}",
year = "2006",
doi = "10.1007/11841036_40",
language = "English (US)",
isbn = "3540388753",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "432--443",
booktitle = "Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings",
note = "14th Annual European Symposium on Algorithms, ESA 2006 ; Conference date: 11-09-2006 Through 13-09-2006",
}