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