Lecture by Tibor Szabó (Freie Universität Berlin): Topology at the North Pole
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 restricted variant, also known as the Santa Claus problem, where each resource 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 approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations 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 allocation problem. This approach yields substantial improvements in the integrality 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.
Before the talk, at 15:30, there will be a tea "break" at the usual place, Room 134 in the first floor (glass door, facing the exit from the stairway).
Time & Location
Jun 26, 2023 | 04:00 PM s.t.
Freie Universität Berlin
Institut für Informatik
Great Lecture Hall (Ground Floor)