Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Approximating independent set in perturbed graphs

 
: Manthey, B.; Plociennik, K.

:

Faigle, U.:
9th Cologne/Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010. Special Issue : Cologne, Germany, between the 25th and the 27th of May, 2010
Amsterdam: Elsevier, 2013 (Discrete applied mathematics 161.2013, Nr.12)
pp.1761-1768
Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW) <9, 2010, Cologne>
English
Conference Paper, Journal Article
Fraunhofer ITWM ()

Abstract
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 epsilon. Our algorithm guarantees an approximation ratio of Omikron(root of n epsilon) for sufficiently large epsilon .

: http://publica.fraunhofer.de/documents/N-254577.html