Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole

Penny Haxell, Tibor Szabó

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 i…