Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOM SUBPROGRAMS:
Reports tagged with Random Subprograms:
TR06-104 | 25th August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

On the Sample Complexity of MAX-CUT

We give a simple proof for the sample complexity bound $O~(1/\epsilon^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.

more >>>



ISSN 1433-8092 | Imprint