Loading...
Please wait, while we are loading the content...
Similar Documents
Approximating almost all instances of max-cut within a ratio above the håstad threshold (2006).
| Content Provider | CiteSeerX |
|---|---|
| Author | Kirousis, L. M. Kaporis, A. C. Stavropoulos, E. C. |
| 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 n⌋) outputs a cut of G whose ratio (in cardinality) 2 with the maximum cut is at least 0.952. We remind the reader that it is known that unless P=NP, for no constant ɛ>0isthereaMax-Cut approximation algorithm that for all inputs achieves an approximation ratio of (16/17) + ɛ (16/17 < 0.94118). |
| File Format | |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Maximum Cut Average Degree Random Graph Deterministic Polynomial-time Algorithm Astad Threshold Approximation Ratio Max-cut Within Constant 0isthereamax-cut Approximation Algorithm Almost Instance |
| Content Type | Text |
