[Facets-of-complexity] Invitation to Monday Lecture on June 26, 16:00 s.t.: Topology at the North Pole / max-min allocation / Santa Claus problem

[Günter Rote <rote@inf.fu-berlin.de>]

Our next Monday Lecture takes place on June 26 at 16:00 sharp at FU Berlin.

*_Location_*

*Great Lecture Hall - Ground Floor*
Freie Universität Berlin
Takustr. 9
14195 Berlin

*_Time_: *Monday, June 26, 2023, 16:00*

*_Lecture_: Tibor Szabó (FU Berlin)

*_Title_: Topology at the North Pole

*_Abstract_:*

In the max-min allocation problem, disjoint subsets of a set R of indivisible
resources are to be allocated to a set P of players, 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.

*_Tea break_:*

Before the talk, at 15:30, there will be a "tea break" at the usual place,
Room 134 (glass door, straight from the stairs) in the first floor.