Improving Christofides' Algorithm for the s-t Path TSP
Speaker: | Hyung-Chan An |
---|---|
Affiliation: | Cornell University |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
We
present
a
deterministic
(1+
√
5
)/2-approximation
algorithm
for
the
s-t
path
TSP
for
an
arbitrary
metric.
Given
a
symmetric
metric
cost
on
n
vertices
including
two
prespecified
endpoints,
the
problem
is
to
find
a
shortest
Hamiltonian
path
between
the
two
endpoints;
Hoogeveen
showed
that
the
natural
variant
of
Christofides'
algorithm
is
a
5/3-approximation
algorithm
for
this
problem,
and
this
asymptotically
tight
bound
in
fact
has
been
the
best
approximation
ratio
known
until
now.
We
modify
this
algorithm
so
that
it
chooses
the
initial
spanning
tree
based
on
an
optimal
solution
to
the
Held-Karp
relaxation
rather
than
a
minimum
spanning
tree;
we
prove
this
simple
but
crucial
modification
leads
to
an
improved
approximation
ratio,
surpassing
the
20-year-old
barrier
set
by
the
natural
Christofides'
algorithm
variant.
Our
algorithm
also
proves
an
upper
bound
of
(1+
√
5
)/2
on
the
integrality
gap
of
the
path-variant
Held-Karp
relaxation.
The
techniques
devised
in
this
paper
can
be
applied
to
other
optimization
problems
as
well:
these
applications
include
improved
approximation
algorithms
and
improved
LP
integrality
gap
upper
bounds
for
the
prize-collecting
s-t
path
problem
and
the
unit-weight
graphical
metric
s-t
path
TSP.
This
is
joint
work
with
Bobby
Kleinberg
and
David
B.
Shmoys.