For a positive integer \(k \ge 1\) , a k-star ( \(k^+\) -star, \(k^-\) -star, respectively) is a connected graph containing a degree- \(\ell \) vertex and \(\ell \) degree-1 vertices, where \(\ell = k\) ( \(\ell \ge k\) , \(1 \le \ell \le k\) , respectively). The \(k^+\) -star packing problem is to cover as many vertices of an input graph G as possible using vertex-disjoint \(k^+\) -stars in G; and given \(k > t \ge 1\) , the \(k^-/t\) -star packing problem is to cover as many vertices of G as possible using vertex-disjoint \(k^-\) -stars but no t-stars in G. Both problems are NP-hard for any fixed \(k \ge 2\) . We present a \((1 + \frac{k^2}{2k+1})\) - and a \(\frac{3}{2}\) -approximation algorithms for the \(k^+\) -star packing problem when \(k \ge 3\) and \(k = 2\) , respectively, and a \((1 + \frac{1}{t + 1 + 1/k})\) -approximation algorithm for the \(k^-/t\) -star packing problem when \(k > t \ge 2\) . They are all local search algorithms and they improve the best known approximation algorithms for the problems, respectively.