In the *k*-Set Packing problem we are given a universe and a family of its subsets, where each of the subsets has size at most *k*. The goal is to select a maximum number of sets from the family which are pairwise disjoint. It is a well known NP-hard problem, that has been studied from the approximation perspective since the 80's. During the talk I will describe the history of progress on both the weighted and unweighted variants of the problem, with an exposition of methods used to obtain the best known approximation algorithms mostly involving local search based routines.

May 28, 2018 | 02:15 PM

Technische Universität Berlin

Institut für Mathematik

Straße des 17. Juni 136

10623 Berlin

room MA 041 (ground floor)

Campus map