Studying Edmonds' trick of bi-directing edges
| Speaker: | Ahmad Abdi |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
A
classic
well-studied
problem
in
combinatorial
optimization
is
that
of
finding
a
minimum
weight
spanning
tree
of
a
graph.
An
optimization-oriented
approach
is
to
use
the
cut
linear
programming
(LP)
relaxation,
except
that
this
LP
is
quite
weak,
outputting
fractional
optimal
solutions
even
on
a
triangle.
In
1967,
Edmonds
came
up
with
a
nifty
trick
to
avoid
this
issue:
bi-direct
the
edges
and
instead,
in
an
equivalent
manner,
look
for
a
minimum
weight
arborescence.
He
showed
that
the
corresponding
bi-directed
cut
LP
relaxation
is
strong,
in
the
sense
that
it
can
always
output
an
integral
optimal
solution.
In
this
talk,
I
will
generalize
Edmonds'
operation
to
any
set
covering
LP,
and
show
how
this
operation
always
makes
the
LP
stronger.
We
will
survey
the
different
attributes
of
this
operation,
and
along
the
way,
we
make
some
beautiful
connections
to
the
extension
complexity
of
vertex
covers,
Steiner
trees,
projective
planes
and
binary
clutters.
I
will
end
with
some
open
questions
on
the
packing
property
and
on
matroid
bases.
Joint
work
with
Ricardo
Fukasawa
and
Laura
Sanità.