# Large Neighborhood Local Search for the Maximum Set Packing Problem

arXiv: https://arxiv.org/abs/1302.4347 · HTML: https://mlsanity.com/paper/1302.4347/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2013.

## Built on by (most cited first, 1 of 1)

- [Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates](https://mlsanity.com/paper/2609.17951/) (2026)

## Abstract (arXiv)

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.