科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 O(root n epsilon) for sufficiently large epsilon.
- 出版日期2013-8
