A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.

Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld

Browse the full SODA paper archive.