Adam Schill Collberg: Combinatorial Optimization and k-Set Packing

For many interesting combinatorial optimization problems there are no known exact algorithms running faster than exponential time (in the input size), and it is a vast research area to try improve the running times of such algorithms. Another big research direction is to study algorithms which approximately solves these hard problems, but achieving better running times (e.g. polynomial time).

In this talk I will begin by introducing the concepts of exact and approximate algorithms. Then I will on a high level review the progress within each of these research areas in the context of a classic and well-studied problem: k-Set Packing (k-uniform hypergraph matching). Lastly we shall look at some techniques used in approximation algorithms, and in particular when applied to the k-Set Packing problem.