Large Neighborhood Local Search for the Maximum Set Packing Problem

In this paper we consider the classical maximum set packing problem where set cardinality is upper bounded by k. We show how to design a variant of a polynomial-time local search algorithm with performance guarantee (k+2)/3. This local search algorithm is a special case of a more general procedure that allows to swap up to Theta(log n) elements per iteration. We also design problem instances with locality gap k/3 even for a wide class of exponential time local search procedures, which can swap up to cn elements for a constant c. This shows that our analysis of this class of algorithms is almost tight.