Title: What's on TAP?
| Speaker: | Joseph Cheriyan |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
In
the
unweighted
Tree
Augmentation
problem
(abbreviated
TAP)
we
are
given
a
2-edge
connected
graph
G
and
a
spanning
tree
T.
The
goal
is
to
find
a
set
of
edges
F
of
minimum
size
(where
F
is
disjoint
from
T)
such
that
the
graph
T+F
is
2-edge
connected.
Zhihan
Gao
(Ph.D.
thesis)
proves
an
approximation
guarantee
relative
to
an
SDP
relaxation
by
analyzing
a
combinatorial
algorithm;
the
SDP
relaxation
is
obtained
from
an
LP
by
applying
Lift-and-Project.
The
talk
will
present
an
overview.