Department of Computer Science
 
Chair V

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