|Type of publication:||Inproceedings|
|Title||Approximating almost all instances of Max-Cut within a ratio above the Hastad threshold|
|Bibtex cite ID||RACTI-RU1-2006-65|
|Booktitle ||14th Annual European Symposium on Algorithms (ESA 2006)|
|Series ||Lecture Notes in Computer Science|
|Year published ||2006|
|Publisher ||Springer, L.N Computer Science|
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).