In this paper we consider the classical maximum set packing problem where set cardinality is upper bounded by a constant 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 Θ(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.
展开▼
