@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",

}