Large Neighborhood Local Search for the Maximum Set Packing Problem

Original · EN

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 Θ(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.