IMPROVED APPROXIMATIONS FOR MAXIMUM INDEPENDENT SET VIA APPROXIMATIONCHAINS

We first define the notion of approximation chain and then we use it t o obtain, in polynomial time, asymptotic approximation ratio of min{ka ppa/mu, [kappa'log(log Delta)]/Delta} (where kappa is a fixed positive constant, kappa' is a constant depending on kappa, and Delta, mu are the maximum and the average degrees of the graph, respectively). This result essentially improves, from both complexity and approximation qu ality points of view, the best-known approximation ratio for maximum i ndependent set.