BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: In the max-min allocation problem a set  P  of players are to 
 be allocated disjoint subsets of a set  R  of indivisible resources\, such 
 that the minimum utility among all players is maximized. We study the restr
 icted variant\, also known as the  Santa Claus problem \, where each resour
 ce has an intrinsic positive value\, and each player covets a subset of the
  resources. Bezakova and Dani showed that this problem is NP-hard to approx
 imate within a factor less than 2\, consequently a great deal of work has f
 ocused on approximate solutions. The principal approach for obtaining appro
 ximation algorithms has been via the Configuration LP (CLP) of Bansal and S
 viridenko. Accordingly\, there has been much interest in bounding the integ
 rality gap of this CLP. The existing algorithms and integrality gap estimat
 ions are all based one way or another on the combinatorial augmenting tree 
 argument of Haxell for finding perfect matchings in certain hypergraphs.   
 Here we introduce the use of topological tools for the restricted max-min a
 llocation problem. This approach yields substantial improvements in the int
 egrality gap of the CLP. In particular we improve the previously best known
  bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell.
  
DTSTAMP:20230619T160000
DTSTART:20230626T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Great Lecture Hall (Ground Floor)
SEQUENCE:0
SUMMARY:Tibor Szabó (FU Berlin): Topology at the North Pole
UID:134466342@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20230626-L-Szabo.html
END:VEVENT
END:VCALENDAR