Article ID Journal Published Year Pages File Type
420008 Discrete Applied Mathematics 2013 8 Pages PDF
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 nn vertices, and then edges are flipped with a probability of εε. Our algorithm guarantees an approximation ratio of O(nε) for sufficiently large εε.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,