An Improved Integrality Gap for Asymmetric TSP Paths

The Asymmetric Traveling Salesperson Path (ATSPP) problem is one where, given an

asymmetric

metric space (

V

,

d

) with specified vertices

s

and

t

, the goal is to find an

s

-

t

path of minimum length that visits all the vertices in

V

.

This problem is closely related to the Asymmetric TSP (ATSP) problem, which seeks to find a tour (instead of an

s

-

t

path) visiting all the nodes: for ATSP, a

ρ

-approximation guarantee implies an

O

(

ρ

)-approximation for ATSPP. However, no such connection is known for the

integrality gaps

of the linear programming relxations for these problems: the current-best approximation algorithm for ATSPP is

O

(log

n

/loglog

n

), whereas the best bound on the integrality gap of the natural LP relaxation (the subtour elmination LP) for ATSPP is

O

(log

n

).

In this paper, we close this gap, and improve the current best bound on the integrality gap from

O

(log

n

) to

O

(log

n

/loglog

n

). The resulting algorithm uses the structure of narrow

s

-

t

cuts in the LP solution to construct a (random) tree witnessing this integrality gap. We also give a simpler family of instances showing the integrality gap of this LP is at least 2.