Title: When is the set covering polyhedron integral?
| Speaker: | Ahmad Abdi |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
A
0,1
matrix
is
perfect
if
its
set
packing
polyhedron
is
integral,
and
it
is
ideal
if
its
set
covering
polyhedron
is
integral.
The
Strong
Perfect
Graph
Theorem
provides
a
characterization
of
perfect
matrices.
Is
there
such
a
characterization
of
ideal
matrices?
So
far,
there
has
not
been
any...
In
1976,
Seymour
proved
that
a
0,1
matrix
is
either
so-called
binary
or
it
is
very
fragile
and
close
to
being
non-ideal.
A
year
later,
he
conjectured
a
characterization
for
binary
matrices
that
are
ideal;
his
conjecture
is
now
known
as
the
f-Flowing
Conjecture.
Guenin
and
I
have
been
working
on
this
conjecture
for
the
past
couple
of
years;
I
will
report
on
our
progress
so
far.
As
far
as
I
know,
there
is
no
road
map
for
characterizing
when
non-binary
matrices
are
ideal.
I
will
talk
about
some
tools
developed
in
joint
work
with
Fukasawa
and
Sanità,
and
in
joint
work
with
Pashkovich,
that
I
think
will
help
in
this
direction.