The Set Packing and Set Covering Polyhedra
| Speaker: | Ahmad Abdi |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
The
set
packing
and
set
covering
polyhedra
are
two
of
the
most
fundamental
objects
in
combinatorial
optimization.
More
than
50
years
of
studying
the
different
properties
of
these
objects
has
led
to
many
beautiful
theories
and
spectacular
results,
such
as
Fulkerson's
theory
of
blocking
and
anti-blocking
polyhedra,
the
different
perfect
graph
theorems,
characterization
of
ideal
matrices,
matroids
with
the
max-flow
min-cut
property,
characterization
of
weakly
bipartite
graphs,
and
many
more.
In
this
talk,
I
will
give
an
overview
of
these
results,
and
explain
the
striking
differences
between
the
two
objects
that
makes
the
set
covering
polyhedron
much
more
complex
than
the
other
one.
I
will
also
talk
about
some
recent
progress
towards
understanding
these
polyhedra.
Some
of
the
results
are
based
on
joint
works
with
A.
Feldmann,
R.
Fukasawa,
B.
Guenin,
J.
Könemann
and
L.
Sanità.