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.