  One of the most natural optimization problems is the k-Set Packing problem,
where given a family of sets of size at most k one should select a maximum size
subfamily of pairwise disjoint sets. A special case of 3-Set Packing is the
well known 3-Dimensional Matching problem. Both problems belong to the Karp`s
list of 21 NP-complete problems. The best known polynomial time approximation
ratio for k-Set Packing is (k + eps)/2 and goes back to the work of Hurkens and
Schrijver [SIDMA`89], which gives (1.5 + eps)-approximation for 3-Dimensional
Matching. Those results are obtained by a simple local search algorithm, that
uses constant size swaps.
  The main result of the paper is a new approach to local search for k-Set
Packing where only a special type of swaps is considered, which we call swaps
of bounded pathwidth. We show that for a fixed value of k one can search the
space of r-size swaps of constant pathwidth in c^r poly(|F|) time. Moreover we
present an analysis proving that a local search maximum with respect to O(log
|F|)-size swaps of constant pathwidth yields a polynomial time (k + 1 +
eps)/3-approximation algorithm, improving the best known approximation ratio
for k-Set Packing. In particular we improve the approximation ratio for
3-Dimensional Matching from 3/2 + eps to 4/3 + eps.
