In this paper, we consider the task of computing an independent set of maximum weight in a given $d$-claw free graph $G=(V,E)$ equipped with a positive weight function $w:V\rightarrow\mathbb{ R}^+$. In doing so, $d\geq 2$ is considered a constant. The previously best known approximation algorithm for this problem is the local improvement algorithm SquareImp proposed by Berman. It achieves a performance ratio of $\frac{ d}{ 2}+\epsilon$ in time $\mathcal{ O}(|V(G)|^{ d+1}\cdot(|V(G)|+|E(G)|)\cdot (d-1)^2\cdot \left(\frac{ d}{ 2\epsilon}+1\right)^2)$ for any $\epsilon>0$, which has remained unimproved for the last twenty years. By considering a broader class of local improvements, we obtain an approximation ratio of $\frac{ d}{ 2}-\frac{ 1}{ 63,700,992}+\epsilon$ for any $\epsilon>0$ at the cost of an additional factor of $\mathcal{ O}(|V(G)|^{ (d-1)^2})$ in the running time. In particular, our result implies a polynomial time $\frac{ d}{ 2}$-approximation algorithm. Furthermore, the well-known reduction from the weighted $k$-Set Packing Problem to the Maximum Weight Independent Set Problem in $k+1$-claw free graphs provides a $\frac{ k+1}{ 2}-\frac{ 1}{ 63,700,992}+\epsilon$-approximation algorithm for the weighted $k$-Set Packing Problem for any $\epsilon>0$. This improves on the previously best known approximation guarantee of $\frac{ k+1}{ 2}+\epsilon$ originating from the result of Berman.
Categories: cs.DS