Approximating independent set in perturbed graphs

For the maximum independent set problem, strong inapproximability bounds for worst-case efficient algorithms exist. We give a deterministic algorithm beating these bounds, with polynomial expected running-time for semi-random graphs: An adversary chooses a graph with $n$ vertices, and then edges are flipped with a probability of $\varepsilon$. Our algorithm guarantees an approximation ratio of $O(\sqrt{n\varepsilon})$ for sufficiently large $\varepsilon$.