On the Sample Complexity of MAX-CUT
Wenceslas Fernandez de la Vega, Marek Karpiński · Electronic colloquium on computational complexity · 2006
We give a simple proof for the sample complexity bound O (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.