Large Neighborhood Local Search for k-Set Packing Problems

4^th February 2014, 16:00 Ashton Lecture Theater
Dr. Justin Ward
Department of Computer Science / Centre for Discrete Mathematics and its Applications (DIMAP)
University of Warwick

Abstract

In the k-set packing problem, we are given a collection C of n sets, each containing at most k elements, and an objective function f assigning a value to each sub-collection S of C. The goal is to find a sub-collection S of pairwise disjoint sets that maximizes the objective value f(S). One of the simplest algorithmic approaches to this problem is local search, in which we repeatedly attempt to add some collection of sets A to S, removing all sets in S that conflict with A, until no such modification improves S. Surprisingly, this general approach gives the best known approximation results for several variants of k-set packing.

In this talk, I shall discuss joint work with Maxim Sviridenko for the unweighted set packing problem (in which f is a cardinality function). We give a large neighborhood local search algorithm that considers at each stage improvements of size proportional to log n. By combining local search with techniques from fixed-parameter tractability, we obtained the first improved polynomial-time approximation algorithm for this problem since Hurkens and Schrijver gave a k/2 approximation in 1989. We also obtain new lower bounds for the performance of local search algorithms that hold even for exponential-time algorithms. I will discuss our techniques, and provide a brief overview of further recent developments in this area.