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