  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.

Data Structures and Algorithms