Tutte Colloquium - Penny HaxellExport this event to calendar

Friday, September 30, 2022 — 3:30 PM EDT

Title: The Integrality Gap for the Santa Claus Problem

Speaker: Penny Haxell
Affiliation: University of Waterloo
Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract: 

In the max-min allocation problem, a set of players are to be allocated disjoint subsets of a set of   indivisible resources, such that the minimum utility among all players is maximized.  In the restricted variant, also known as the Santa Claus Problem,  each resource (``toy'') has an intrinsic positive value, and each player (``child'') covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy
jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.

Bezakova and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the Configuration LP of
Bansal and Sviridenko, and bounds on its integrality gap. The existing algorithms and integrality gap estimations tend to be based one way or another on a combinatorial local search argument for finding perfect matchings in certain hypergraphs.

Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, from the previously best known bound of
3.808 for the general problem to 3.534. We also address the well-studied special case in which resources can take only two values, and improve the
integrality gap in most cases.

This is based on joint work with Tibor Szabo.

Event tags 

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2023 (10)
    1. February (2)
    2. January (8)
  2. 2022 (150)
    1. December (8)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  3. 2021 (103)
  4. 2020 (119)
  5. 2019 (167)
  6. 2018 (136)
  7. 2017 (103)
  8. 2016 (137)
  9. 2015 (136)
  10. 2014 (88)
  11. 2013 (48)
  12. 2012 (39)
  13. 2011 (36)
  14. 2010 (40)
  15. 2009 (40)
  16. 2008 (39)
  17. 2007 (15)