|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-APX-Reports 2006 | Copyright 2006 University of Bonn, Department of Computer Science, Abt. V | |
|
89105 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
|
University of Bonn -> Department of Computer Science -> Chair V | |