Optimizing misdirection
Piotr Berman, Piotr Krysta · Max Planck Institute for Plasma Physics · 2003
In this paper we consider the following problem. Given a (d + 1)-claw free graph G = (V, E, w) where w : V → R+, maximize w(A) where A is an independent set in G. Our focus is to minimize the approximation ratio (optimum/obtained) in polynomial time that does not depend on d. Our approach is to apply local improvements of size 2, using a misdirected criterion, i.e.wα(A) rather than w(A). We find the optimal value of α for every d, and the resulting ratio is roughly 0.667d for d = 3, 0.651d for d = 4 and 0.646d for d > 4.