@inproceedings{8098adf9e7814453bfe5b542427d2062,
title = "Approximating independent set in semi-random graphs",
abstract = "We present an algorithm for the independent set problem on semi-random graphs, which are generated as follows: An adversary chooses an n-vertex graph, and then each edge is flipped independently with a probability of $\varepsilon > 0$. Our algorithm runs in expected polynomial time and guarantees an approximation ratio of roughly $O(\sqrt{\varepsilon n})$, which beats the inapproximability bounds.",
keywords = "METIS-275735, Independent set, Approximation algorithms, EWI-18959, Smoothed Analysis, Random graphs, Semi-random graphs, IR-75055",
author = "Bodo Manthey and Kai Plociennik",
year = "2010",
language = "Undefined",
isbn = "not assigned",
publisher = "University of Cologne",
pages = "119--122",
editor = "U. Faigle and R. Schrader and D. Herrmann",
booktitle = "Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)",
note = "9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 ; Conference date: 25-05-2010 Through 27-05-2010",
}