| Speaker: | Arash Haddadan |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
In
bin
packing
we
want
to
pack
n
items
with
sizes
between
zero
and
one,
in
the
minimum
possible
number
of
bins
of
size
one.
The
main
step
forward
towards
solving
bin
packing
was
made
by
Karmarkar
and
Karp,
transforming
a
fractional
solution
to
Gilmore
Gomory
LP
relaxation
into
an
integral
solution,
by
using
at
most
log(n)^2
additional
bins.
In
this
paper,
for
a
special
case,
where
all
items
have
size
at
least
1/(1+k),
an
upper
bound
on
the
additive
integrality
gap
of
this
LP
relaxation
is
given,
based
on
discrepancy
of
k
permutations.
In
particular,
for
the
case
of
3-partition,
where
all
items
have
size
at
least
1/4,
this
could
have
a
connection
with
a
conjecture
of
Beck,
which
suggests
a
constant
upper
bound
for
the
discrepancy
of
3
permutations.
The
conjecture
was
open
for
decades,
until
a
couple
of
months
after
this
papers
came
out,
a
counterexample
with
a
logarithmic
factor
was
found.
However,
in
the
journal
version
of
the
paper,
they
use
the
counter-example
to
show
that
it
is
impossible
to
improve
the
log(n)^2
factor
if
we
employ
a
rounding-up
procedure.
The
presentation
will
be
based
on
the
following
manuscript:
http://arxiv.org/pdf/1007.2170v2.pdf