Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2006 Copyright 2006 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V