For a positive integer k ≥ 1 , a k -star ( k + -star, k − -star, respectively) is a connected graph containing a degree- ℓ vertex and ℓ degree-1 vertices, where ℓ = k ( ℓ ≥ k , 1 ≤ ℓ ≤ 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 ≥ 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 ≥ 2 . We present a ( 1 + k 2 2 k + 1 ) - and a 3 2 -approximation algorithms for the k + -star packing problem when k ≥ 3 and k = 2 , respectively, and a ( 1 + 1 t + 1 + 1 / k ) -approximation algorithm for the k − / t -star packing problem when k > t ≥ 2 . They are all local search algorithms and they improve the best known approximation algorithms for the problems, respectively.