BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: In the k -Set Packing problem we are given a universe and a f
amily 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 pairwi
se disjoint. It is a well known NP-hard problem\, that has been studied fro
m the approximation perspective since the 80's. During the talk I will desc
ribe the history of progress on both the weighted and unweighted variants o
f the problem\, with an exposition of methods used to obtain the best known
approximation algorithms mostly involving local search based routines.
DTSTAMP:20180611T180600
DTSTART:20180528T141500
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
es 17. Juni 136\n 10623 Berlin\n room MA 041 (ground floor)
SEQUENCE:0
SUMMARY:Marek Cygan (University of Warsaw): Approximation algorithms for th
e k-Set Packing problem
UID:89287610@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20180528-L-Cygan.html
END:VEVENT
END:VCALENDAR