|
|
| |
| Universität Bonn -> Institut für Informatik -> Abteilung V | ||
| CS-Reports 2006 | Copyright 2006 Universität Bonn, Institut für Informatik, Abt. V | |
|
85277 25.08.2006 |
On the Sample Complexity of MAX-CUT
W. Fernandez de la Vega and Marek Karpinski [Download PostScript] [Download PDF] We give a simple proof for the sample complexity boundO∼(1/ε4) of absolute approximation of MAX-CUT.The proof depends on a new analysis method for linear programs(LPs) underlying MAX-CUT which could be also of independent interest. |
|
|
Last Change:
11/05/14 at 10:35:52
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |