Better s-t-Tours by Gao Trees

arXiv:1511.05514v1 [cs.DM] 17 Nov 2015

Corinna Gottschalk
RWTH Aachen

Jens Vygen

University of Bonn

November 17, 20151

Abstract
We consider the s-t-path TSP: given a ﬁnite metric space with two elements s and t, we
look for a path from s to t that contains all the elements and has minimum total distance.
We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous
algorithms, we solve the natural LP relaxation and represent an optimum solution x∗ as a
convex combination of spanning trees. Gao showed that there exists a spanning tree in the
support of x∗ that has only one edge in each narrow cut (i.e., each cut C with x∗ (C) < 2).
Our main theorem says that the spanning trees in the convex combination can be chosen such
that many of them are such “Gao trees”.
keywords: traveling salesman problem, s-t-path TSP, approximation algorithm, spanning
tree

1

Introduction

The traveling salesman problem (TSP) is one of the best-known NP-hard problems in combinatorial optimization. In this paper, we consider the s-t-path variant: Given a ﬁnite set V (of cities),
two elements s, t ∈ V and c : V × V → R≥0 , the goal
is to ﬁnd a sequence v1 , . . . , vN containing
PN
−1
all cities and with v1 = s and vN = t, minimizing i=1
c(vi , vi+1 ). An equivalent formulation
requires that every city is visited exactly once, but then we need to assume that c satisﬁes the
triangle inequality. We work with the latter formulation (to obtain such an instance from a general
function c, compute the metric closure). The special case where s = t is the well-known metric
TSP; but in this paper we assume s 6= t.
The classical algorithm by Christoﬁdes [1976] computes a minimum-cost spanning tree (V, S) and
then does parity correction by adding a minimum-cost matching on the vertices whose degree
in S has the wrong parity. While Christoﬁdes’ algorithm is still the best known approximation
algorithm for metric TSP (with ratio 32 ), there have recently been improvements for special cases
and variants (see e.g. Vygen [2012] for a survey), including the s-t-path TSP.
1

This work was done during the trimester program on combinatorial optimization at the Hausdorff Institute for
Mathematics in Bonn.

1

1.1

Previous Work

For the s-t-path TSP, Christoﬁdes’ algorithm has only an approximation ratio of 35 as shown by
Hoogeveen [1991]. An, Kleinberg
and Shmoys [2015] were the ﬁrst to improve on this and obtained
√
1+ 5
an approximation ratio of 2 ≈ 1.618. They ﬁrst solve the natural LP relaxation (essentially
proposed by Dantzig, Fulkerson and Johnson [1954]) and represent an optimum solution x∗ as a
convex combination of spanning trees. This idea, ﬁrst proposed by Held and Karp [1970], was exploited earlier for diﬀerent TSP variants by Asadpour et al. [2010] and Oveis Gharan, Saberi and Singh
[2011]. Given this convex combination, An, Kleinberg and Shmoys [2015] do parity correction for
each of the contributing trees and output the best of these solutions. Sebő [2013] improved the
analysis of this best-of-many Christofides algorithm and obtained the approximation ratio 58 . Gao
[2015] gave a uniﬁed analysis. Vygen [2015] suggested to “reassemble” the trees: starting with an
arbitrary convex combination of spanning trees, he computed a diﬀerent one, still representing x∗ ,
that avoids certain bad local conﬁgurations. This led to the slightly better approximation ratio
of 1.599.
In this paper, we will reassemble the trees more systematically to obtain a convex combination
with strong global properties. This will enable us to control the cost of parity correction much
better, leading to an approximation ratio of 1.566.
This also proves an upper bound of 1.566 on the integrality ratio of the natural LP. The only
known lower bound is 1.5. Sebő and Vygen [2014] proved that the integrality ratio is indeed 1.5
for the graph s-t-path TSP, i.e., the special case of graph metrics (where c(v, w) is the distance
from v to w in a given unweighted graph on vertex set V ). Gao [2013] gave a simpler proof of this
result, which inspired our work: see Section 1.4.

1.2

Notation and Preliminaries

Throughout this paper, V denotes the given set of cities, n := |V |, and E denotes the set of
edges of the complete graph on V . Moreover, c : V × V → R≥0 is the given metric. For any
U ⊆ V we write E[U ] for the set of edges with both endpoints in U and δ(U ) for the set of edges
with exactly one endpoint in U ; moreover, δ(v) := δ({v}) for v ∈ V . If F ⊆ E and U ⊆ V ,
we denote by (V, F )[U ] the subgraph (U, F ∩ E[U ]) of (V, F ) induced by U . For x ∈ RE
≥0 we
P
P
F
write c(x) := e={v,w}∈E c(v, w)xe and x(F ) := e∈F xe for F ⊆ E. Furthermore, χ ∈ {0, 1}E
denotes the characteristic vector of a subset F ⊆ E, and c(F ) := c(χF ). For F ⊂ E and f ∈ E,
we write F + f and F − f for F ∪ {f } and F \ {f }, respectively.
For T ⊆ V with |T | even, a T -join is a set J ⊆ E for which |δ(v) ∩ J| is odd if and only if v ∈ T .
Edmonds [1965] proved that a minimum weight T -join can be computed in polynomial time.
Moreover, the minimum cost of a T -join is the minimum over c(y) for y in the T -join polyhedron
{y ∈ RE
≥0 : y(δ(U )) ≥ 1 ∀U ⊂ V with |U ∩ T | odd} as proved by Edmonds and Johnson [1973].
We are going to use that the cost of any vector in the T -join polyhedron is an upper bound for
the minimum cost of a T -join.
2

To obtain a solution for the s-t-path TSP, it is suﬃcient to compute a connected multi-graph
with vertex set V in which exactly s and t have odd degree. We call such a graph an {s, t}-tour.
As an {s, t}-tour contains an Eulerian walk from s to t, we can obtain a Hamiltonian s-t-path
(i.e. an s-t-path with vertex set V ) by traversing the Eulerian walk and shortcutting when the
walk encounters a vertex that has been visited already. Since c is a metric, it obeys the triangle
inequality. Thus, the resulting path is not more expensive than the multigraph.
By S we denote the set of edge sets of spanning trees in (V, E). For S ∈ S, TS denotes the
set of vertices whose degree has the wrong parity, i.e., even for s or t and odd for v ∈ V \
{s, t}. Christoﬁdes’ algorithm computes an S ∈ S with minimum c(S) and adds a TS -join J with
minimum c(J).

1.3

Best-of-Many Christofides

Like An, Kleinberg and Shmoys [2015], we begin by solving the natural LP relaxation:
min c(x)
subject to

x(δ(U ))
x(δ(U ))
x(δ(v))
x(δ(v))
xe

≥
≥
=
=
≥

(∅ =
6 U ⊂ V, |U ∩ {s, t}| even)
(∅ =
6 U ⊂ V, |U ∩ {s, t}| odd)
(v ∈ V \ {s, t})
(v ∈ {s, t})
(e ∈ E)

2
1
2
1
0

(1)

whose integral solutions are precisely the incidence vectors of the edge sets of the Hamiltonian
s-t-paths in (V, E). This LP can be solved in polynomial time (either by the ellipsoid method
(Grötschel, Lovász and Schrijver [1981]) or an extended formulation). Let x∗ be an optimum
solution. Then, x∗ (in factPevery feasible solution) can be written as convex combination of
S
∗
spanning
P trees, i.e. as x = S∈S pS χ , where p is a distribution on S, i.e., pS ≥ 0 for all S ∈ S
and S∈S pS = 1.
By Carathéodory’s theorem, we can assume that pS > 0 for less than n2 spanning trees (V, S).
Such spanning trees and numbers pS can be computed in polynomial time, using either the ellipsoid
method or the splitting-oﬀ technique (cf. Genova and Williamson [2015]).
The best-of-many Christoﬁdes algorithm does
the following: Compute an optimum solution x∗ for
P
(1) and obtain a distribution p with x∗ = S∈S pS χS as above. For each tree (V, S) with pS > 0,
˙ S ) is an {s, t}-tour. We
compute a minimum weight TS -join JS . Then, the multigraph (V, S ∪J
output the best of these.
We will ﬁx x∗ henceforth. An important concept in An, Kleinberg and Shmoys [2015] and the
subsequent works are the so-called narrow cuts, i.e., the cuts C = δ(U ) with x∗ (C) < 2. We
denote by C the set of all narrow cuts. We are going to exploit their structure as well.

3

Lemma 1 (An, Kleinberg and Shmoys [2015]) The narrow cuts form a chain: there are sets
{s} = U0 ⊂ U1 ⊂ · · · ⊂ Uℓ−1 ⊂ Uℓ = V \ {t} so that C = {δ(Ui ) : i = 0, . . . , ℓ}. These sets can be
computed in polynomial time.
We number the narrow cuts C = {C0 , C1 . . . , Cℓ } with Ci = δ(Ui ) (i = 0, . . . , ℓ).

1.4

Gao trees

Our work was inspired by the following idea of Gao [2013]:
Theorem 2 (Gao [2013]) There exists a spanning tree S ∈ S with x∗e > 0 for all e ∈ S and
|C ∩ S| = 1 for all C ∈ C.
In fact, Gao [2013] showed this for any vector x ∈ RE
6 U ⊂ V and
≥0 with x(δ(U )) ≥ 1 for all ∅ =
x(δ(U )) ≥ 2 for all ∅ =
6 U ⊂ V with |U ∩ {s, t}| even. For graph s-t-path TSP, one uses only
variables corresponding to edges of the given graph. Then every spanning tree has cost n − 1. The
approximation guarantee of 32 then follows from the fact that for a tree (V, S) with |S ∩ C| = 1
for all C ∈ C, the vector 21 x∗ is in the TS -join polyhedron. But, as shown by Gao [2015], for the
general s-t-path TSP there may be no tree as in Theorem 2 whose cost is bounded by the LP
value.
Let us call a tree S ∈ S a local Gao tree at C if |C ∩ S| = 1. We call S a global Gao tree if it is a
local Gao tree at every narrow cut.
An, Kleinberg
and Shmoys [2015] and Sebő [2013] observed that for every distribution p with
P
x∗ = S∈S pS χS and every narrow cut C ∈ C, at least a 2 − x∗ (C) fraction of the trees will be
local Gao trees at C. However, in general none of these trees will be a global Gao tree.

1.5

Our contribution

Our main contribution is a new structural result: Starting from an arbitrary distribution of trees
representing x∗ , we can compute a new distribution in which a suﬃcient number of trees are Gao
trees simultaneously for all suﬃciently narrow cuts. For example, if x∗ (C) = 32 for all C ∈ C, at
least half of our new distribution will be made of global Gao trees. Here is our main structure
theorem:
Theorem
solution
x∗ of (1), there are S1 , . . . , Sr ∈ S and p1 , . . . , pr > 0
Pr 3 For every feasible
Pr
∗
with j=1 pj = 1 such that x = j=1 pj χSj and for every C ∈ C there exists a k ∈ {1, . . . , r}
P
with kj=1 pj ≥ 2 − x∗ (C) and |C ∩ Sj | = 1 for all j = 1, . . . , k.

Note that this result immediately implies Theorem 2, simply by taking S1 .
However, we do not know whether such a distribution can be computed in polynomial time (or even
whether r can be polynomially bounded). Therefore we will start with an arbitrary distribution p
4

and round the coeﬃcients down to integral multiples of nǫ3 for a suﬃciently small constant ǫ > 0.
P
3
This way we will get a vector x close to x∗ that we can write as x = rj=1 1r χSj , where r ≤ nǫ
and Sj ∈ S for j = 1, . . . , r. We will work with x in the following and consider the rounding error
in Section 3. We will show that x ∈ RE
≥0 satisﬁes the properties
x(δ(s)) = x(δ(t)) = 1

and

x∗ (F ) − ǫ ≤ x(F ) ≤ x∗ (F ) + ǫ for all F ⊆ E.

(2)

Theorem 4 Given S1 , . . . , Sr ∈ S, a feasible solution x∗ of (1) and ǫ ≥ 0 such that x =
Pr
1 Pr
Sj satisfies (2), we can find Ŝ , . . . , Ŝ ∈ S in polynomial time such that x = 1
Ŝj
1
r
j=1 χ
j=1 χ ,
r
r
and for every C ∈ C there exists an h ∈ {1, . . . , r} with hr ≥ 2 − x∗ (C) − ǫ and |C ∩ Ŝj | = 1 for
all j = 1, . . . , h.
P
Sj =
Note
this theorem implies Theorem 3, by letting ǫ = 0 and x = x∗ =
S∈S pS χ
Pr that
1
1 Sj
where all pS are integer multiples of r for some (possibly exponentially large) natural
j=1 r χ
number r and taking rpS copies of each S ∈ S.
This paper is organized as follows: In Section 2, we will prove Theorem 4. In Section 3, we will
analyze the best-of-many Christoﬁdes algorithm on the resulting distribution. Finally, in Section
4 we provide the computations needed to obtain the approximation guarantee of 1.566.

2

Proof of the Structure Theorem

P
We will prove Theorem 4 by starting with arbitrary trees S1 , . . . , Sr ∈ S with x = 1r rj=1 χSj
satisfying (2), and successively exchange a pair of edges in two of the trees. We will ﬁrst satisfy
the properties for the ﬁrst tree S1 , then for S2 , and so on. For each Sj , we will work on the narrow
cuts C1 , . . . , Cℓ−1 in this order; note that |C0 ∩ Sj | = |Cℓ ∩ Sj | = 1 always holds for all j = 1, . . . , r
due to the ﬁrst property in (2).
In the following we write
θi := ⌈r(2 − x∗ (Ci ) − ǫ)⌉
for i = 0, . . . , ℓ. Note that θ0 ≥ θi for all i = 1, . . . , ℓ because x∗ (Ci ) ≥ 1 = x∗ (C0 ) = x∗ (δ(s)).
Our goal is to obtain |Sj ∩ Ci | = 1 whenever j ≤ θi .
Note that |Sj ∩ Ci | = 1 implies that (V, Sj )[Ui ] is connected, and we will ﬁrst obtain this weaker
property by Lemma 9, before obtaining |Sj ∩ Ci | = 1 by Lemma 10.
We need a few preparations.
P
Lemma 5 Let S1 , . . . , Sr ∈ S and ǫ ≥ 0 such that x = 1r rj′ =1 χSj′ satisfies (2). Let 0 ≤ h <
i ≤ ℓ and 1 ≤ j ≤ r with j ≤ θh and j ≤ θi . Let M = Ui \ Uh or M = Ui . Then there exists an
index k ≥ j such that (V, Sk )[M ] is connected.

5

Proof: Assume the above is not true. Then |E[M ] ∩ Sj ′ | ≤ |M | − 1 for all j ′ < j, and |E[M ] ∩
Sj ′ | ≤ |M | − 2 for j ′ ≥ j. Therefore,
P
x(E[M ]) = 1r rj′ =1 |E[M ] ∩ Sj ′ |

≤ 1r (j − 1)(|M | − 1) + (r − j + 1)(|M | − 2) = |M | − 2 + j−1
r .

P
∗
∗
On the other hand, using (2) we have x(E[M ]) + ǫ ≥ x∗ (E[M ]) = 21
v∈M x (δ(v)) − x (δ(M )) .
If M = Ui \Uh , this is equal to |M |− 21 (x∗ (Ch )+x∗ (Ci ))+x∗ (Ch ∩Ci ) ≥ |M |− 21 (x∗ (Ch )+x∗ (Ci )).
If M = Ui , this is equal to |M | − 21 − 12 x∗ (Ci ) = |M | − 12 (1 + x∗ (Ci )).
j−1
∗
Now, j ≤ θi and j ≤ θh implies 1 ≤ x∗ (Ci ) < 2 − j−1
r − ǫ and x (Ch ) < 2 − r − ǫ. Thus,
x(E[M ]) > −ǫ + |M | − 12 (2 −

j−1
r

−ǫ+2−

j−1
r

a contradiction.

− ǫ) = |M | − 2 +

j−1
r ,

✷

P
Lemma 6 Let S1 , . . . , Sr ∈ S and ǫ ≥ 0 such that x = 1r rj′ =1 χSj′ satisfies (2). Let 0 ≤ h <
i ≤ ℓ and 1 ≤ j ≤ r with j ≤ θh and j ≤ θi . Then there exists an index k ≥ j such that
Sk ∩ Ch ∩ Ci = ∅.
′
∗
Proof: Using ﬁrst (2) and then x∗ (Ci′ ) < 2 − j−1
r − ǫ for i ∈ {h, i} and x (U ) ≥ 2 for |U ∩ {s, t}|
even, we obtain

x(Ch ∩ Ci ) − ǫ ≤ x∗ (Ch ∩ Ci ) = 21 x∗ (Ch ) + x∗ (Ci ) − x∗ (δ(Ui \ Uh ))

<2−

j−1
r

−ǫ−1=

r−j+1
r

P
Therefore, 1r rj′ =1 |Sj ′ ∩ Ch ∩ Ci | = x(Ch ∩ Ci ) <
edge in Ch ∩ Ci .

− ǫ.

r−j+1
,
r

i.e. at most r − j trees can contain an
✷

P
Lemma 7 Let S1 , . . . , Sr ∈ S and ǫ ≥ 0 such that x = 1r rj′ =1 χSj′ satisfies (2). Let 1 ≤ i ≤ ℓ−1
and j ≤ θi with |Ci ∩ Sj | ≥ 2. Then there exists an index k > θi with |Ci ∩ Sk | = 1.
P
Proof: Suppose there exists no such k. Then we get rx(Ci ) = rj′ =1 |Ci ∩ Sj ′ | ≥ (r − θi +
1)2 + θi − 1 = 2r − ⌈r(2 − x∗ (Ci ) − ǫ)⌉ + 1 > 2r − r(2 − x∗ (Ci ) − ǫ) = r(x∗ (Ci ) + ǫ), which is a
contradiction to (2).
✷
Lemma 8 Let 1 ≤ i ≤ ℓ − 1 and M ⊆ Ui and Sj , Sk ∈ S such that (V, Sj )[M ] is disconnected
and (V, Sk )[M ] is connected and |Sj ∩ δ(Ui \ M )| ≤ 1. Then there exist edges e ∈ Sj and f ∈ Sk
such that Sj − e + f ∈ S and Sk + e − f ∈ S and e ∈
/ E[Ui ] and f ∈ E[M ].

6

Ui
M
A1

B1

e

F
B2

A2

Y

Bq

Aq

Ci
Figure 1: Tree Sj in green, Sk in red/bold. In this example one can choose p = 1. Note that e
could belong to Ci (but not to δ(Ui \ M )).
Proof: An illustration of the following proof can be found in Figure 1. Let A1 , . . . , Aq be the
vertex sets of the
Sqconnected components of (V, Sj )[M ]; note that q ≥ 2.
Let F := Sk ∩ p=1 (δ(Ap ) \ δ(M )) be the set of edges of Sk between the sets A1 , . . . , Aq . Note
that F ⊆ E[M ]. For p = 1, . . . , q let Bp be the set of vertices reachable from Ap in (V, Sk \ F ).
Trivially, Ap ⊆ Bp for all p, and {B1 , . . . , Bq } is a partition of V because (V, Sk )[M ] is connected
and (V, Sk ) is a tree. Let Y be the union of the edge sets of the unique v-w-paths in Sj for all
v, w ∈ M . Note that Y ⊆ E[V \ (Ui \ M )] because |Sj ∩ δ(Ui \ M )| ≤ 1.
Claim: There exists an index p ∈ {1, . . . , q} and an edge e ∈ Y ∩ δ(Bp ) such that for every
p′ ∈ {1, . . . , q} \ {p} the path in Sj from Ap to Ap′ contains e.
To prove the Claim, note that (V, Y ) consists of a treeSand possibly isolated vertices. Choose an
arbitrary root z in this tree and take an edge e ∈ Y ∩ qp′ =1 δ(Bp′ ) with maximum distance from
z.
Let D := {v ∈ V : e is on the z-v-path in (V, Y )}. We will show that D ∩ M = Ap for some
p ∈ {1, . . . , q}. This will immediately imply that p and e satisfy the properties of the Claim.
Observe that D ∩ M 6= ∅. Let v ∈ D ∩ M and p such that v ∈ Ap . Since (V, Sj )[Ap ] is connected,
this implies Ap ⊆ D. (D, Y ∩ E[D]) is a tree and by the choice of e, it contains no edge from
S
q
p′ =1 δ(Bp′ ). Therefore, D ⊆ Bp and hence, D ∩ M = Ap . The Claim is proved.
Now, take an index p and an edge e as in the Claim. Consider the path P in Sk that connects the
endpoints of e. Since e ∈ δ(Bp ), P has an edge f ∈ δ(Bp ) ∩ Sk = δ(Ap ) ∩ F . Thus, (V, Sk + e − f )
7

is a tree. The path in Sj that connects the endpoints of f contains e by the Claim. Thus,
(V, Sj − e + f ) is a tree. We have f ∈ E[M ] since f ∈ F , and e 6∈ E[Ui ] as e ∈ Y ∩ δ(Bp ).
✷
Now we are ready to prove our main lemmas:
P
Lemma 9 Let S1 , . . . , Sr ∈ S and ǫ ≥ 0 such that x = 1r rj′ =1 χSj′ satisfies (2). Let 1 ≤ i ≤ ℓ−1
such that j ≤ θi and |Sj ∩ Ch | = 1 for all h < i with j ≤ θh . Then we can find Ŝ1 , . . . , Ŝr ∈ S in
P
polynomial time such that x = 1r rj′ =1 χŜj′ and Ŝj ′ = Sj ′ for all j ′ < j and |Ŝj ∩ Ch | = 1 for all
h < i with j ≤ θh , and (V, Ŝj )[Ui ] is connected.
Proof: Assume that (V, Sj )[Ui ] is disconnected, i.e., |Sj ∩ E[Ui ]| < |Ui | − 1. Let h be the largest
index smaller than i with j ≤ θh . Such an index must exist because θ0 ≥ θi ≥ j.
Case 1: |Sj ∩ E[Ui \ Uh ]| < |Ui \ Uh | − 1.
Let M := Ui \ Uh . Note that |Sj ∩ δ(Ui \ M )| = |Sj ∩ Ch | = 1. Since (V, Sj )[M ] is not connected,
by Lemma 5 there exists an index k > j such that (V, Sk )[M ] is connected.
Now we apply Lemma 8 and obtain two trees Ŝj := Sj − e + f and Ŝk := Sk + e − f with e ∈
/ E[Ui ]
and f ∈ E[M ].
We have |Ŝj ∩ E[Ui ]| = |Sj ∩ E[Ui ]| + 1 and |Ŝj ∩ Ch′ | ≤ |Sj ∩ Ch′ | for all h′ ≤ h and hence
|Ŝj ∩ Ch′ | = 1 for h′ ≤ h with j ≤ θh′ . Note that j > θi′ for all h < i′ < i, so a new edge f in such
cuts Ci′ does no harm.
We replace Sj and Sk by Ŝj and Ŝk and leave the other trees unchanged. If (V, Ŝj )[Ui ] is still not
connected, we iterate.
Case 2: |Sj ∩ E[Ui \ Uh ]| = |Ui \ Uh | − 1.
(V, Sj )[Uh ] is connected since |Sj ∩ Ch | = 1. Moreover, (V, Sj )[Ui \Uh ] is connected, but (V, Sj )[Ui ]
is disconnected. Therefore, Sj must contain an edge in Ci ∩Ch and Sj ∩Ch ⊂ Sj ∩Ci and (V, Sj )[Ui ]
has exactly two connected components: Uh and Ui \ Uh . We will illustrate the following in Figure
2.
Case 2a: h > 0. Let g be the largest index smaller than h with j ≤ θg . Set M := Ui \ Ug . Note
that |Sj ∩ δ(Ui \ M )| = |Sj ∩ Cg | = 1. By Lemma 5 there exists an index k ≥ j with (V, Sk )[M ]
connected. As (V, Sj )[M ] is not connected, we have k > j.
Case 2b: h = 0. Set M := Ui . Note that |Sj ∩ δ(Ui \ M )| = |Sj ∩ δ(∅)| = 0. By Lemma 5, there
exists an index k ≥ j such that (V, Sk )[M ] is connected. Since (V, Sj )[M ] is not connected, k > j.
Note that in both cases 2a and 2b, (V, Sj )[M ] is disconnected. Now we apply Lemma 8 and obtain
two trees Ŝj := Sj − e + f and Ŝk := Sk + e − f with e ∈
/ E[Ui ] and f ∈ E[M ]. We replace Sj and
Sk by Ŝj and Ŝk and leave the other trees unchanged. Then (V, Sˆj )[Ui ] is connected. We have
|Ŝj ∩ Ch′ | = 1 for all h′ < h with j ≤ θh′ , but we may have |Ŝj ∩ Ch | = 2.
Assume |Ŝj ∩ Ch | = 2 (otherwise we are done). Then Ŝj ∩ Ch ∩ Ci = Sj ∩ Ch ∩ Ci = Sj ∩ Ch ,
and this set contains precisely one edge ê = {v, w} (where v ∈ Uh and w ∈ V \ Ui ). By Lemma 6
there exists an index k′ > j with Ŝk′ ∩ Ch ∩ Ci = ∅.
8

M
connected in Sj

v

w
ê

W

f

Ch

Ci

Figure 2: Tree Sj in green, Ŝk′ in red/bold. The dashed edge f is added to Sj by applying Lemma
8.
Let W be the set of vertices reachable from w in (V, Ŝj \ Ci ). Since (V, Ŝj )[Ui ] is connected,
Ŝj ∩ δ(W ) = {ê}. The unique path in (V, Ŝk′ ) from v to w contains at least one edge fˆ ∈ δ(W ).
ˆ
ˆ
Note that fˆ ∈
/ Ch by the choice of Ŝk′ . We replace Ŝj and Ŝk′ by Ŝj := Ŝj − ê + fˆ and Ŝk′ :=
ˆ
ˆ
Ŝk′ + ê − fˆ. Then (V, Ŝj )[Ui ] is still connected and |Ŝj ∩ Ch′ | = 1 for all h′ < i with j ≤ θh′ . ✷
P
Lemma 10 Let S1 , . . . , Sr ∈ S and ǫ ≥ 0 such that x = 1r rj′ =1 χSj′ satisfies (2). Let 1 ≤ i ≤
ℓ − 1 and j ≤ θi such that (V, Sj )[Ui ] is connected and |Sj ∩ Ch | = 1 for all h < i with j ≤ θh .
P
Then we can find Ŝ1 , . . . , Ŝr ∈ S in polynomial time such that x = 1r rj′ =1 χŜj′ and Ŝj ′ = Sj ′ for
all j ′ < j and |Ŝj ∩ Ch | = 1 for all h ≤ i with j ≤ θh .
Proof: Suppose |Sj ∩ Ci | ≥ 2. Then by Lemma 7 there exists an index k > θi with |Sk ∩ Ci | = 1.
We will swap a pair of edges, reducing |Sj ∩ Ci | and increasing |Sk ∩ Ci | while maintaining the
other properties. An illustration of the following construction is given in Figure 3.
Let Sk ∩ Ci = {{x, y}} with x ∈ Ui and y ∈ V \ Ui . Let A be the set of vertices reachable from
y in (V, Sj \ Ci ). Note that A ∩ Ui = ∅. We have |δ(A) ∩ Sj ∩ Ci | = 1 because (V, Sj )[Ui ] is
connected. So let e = {v, w} ∈ (Sj ∩ Ci ) \ δ(A), with v ∈ Ui and w ∈ V \ Ui . Let B be the set of
vertices reachable from w in (V, Sj \ Ci ). We have w ∈ B, y ∈ A, and A ∩ B = ∅ by the choice of
e. Consider the path P in Sk from w to y. Note that P does not contain any vertex in Ui because
|Ci ∩ Sk | = 1. But P contains at least one edge f ∈ δ(B).
We will swap e and f . Since Sk ∩ Ci = {{x, y}}, the w-v-path in Sk contains P . Therefore,
Ŝk := Sk + e − f is a tree. On the other hand, the path in Sj connecting the endpoints of f must
use an edge in δ(B). Since Sj ∩ E[Ui ] is connected and Sj ∩ (δ(B) \ Ci ) = ∅, e is the only edge in
δ(B) ∩ Sj and thus, Ŝj := Sj + f − e is a tree.

9

B
v

e

w

f

P
y

x

A
Ci

Figure 3: Tree Sj in green, Sk in red/bold
Since f ∈ E[V \ Ui ] and e ∈ Ci , we have |Ŝj ∩ Ci | = |Sj ∩ Ci | − 1 and |Ŝj ∩ Ch | = |Sj ∩ Ch | for all
h < i with j ≤ θh . Moreover, (V, Ŝj )[Ui ] is still connected. As before, we replace Sj and Sk by Ŝj
and Ŝk and leave the other trees unchanged. If |Ŝj ∩ Ci | > 1, we iterate.
✷
Now the proof of Theorem 4 is a simple induction. We scan the indices of the trees j = 1, . . . , r
in this order. For each j, we consider all narrow cuts Ci with j ≤ θi . Since x satisﬁes (2), we
always have |Sj ∩ C0 | = 1 and |Sj ∩ Cℓ | = 1 for all j = 1, . . . , r. Now let i ∈ {1, . . . , ℓ − 1} with
j ≤ θi . Assuming |Sj ∩ Ch | = 1 for all h < i with j ≤ θh , we ﬁrst apply Lemma 9 and then Lemma
10. The new tree then satisﬁes |Sj ∩ Ch | = 1 for all h ≤ i with j ≤ θh , and S1 , . . . Sj−1 remain
unchanged.

3

Analysis of the Approximation Ratio

In this section, we will explain and analyze the algorithm that was sketched in Section 1. As
mentioned before, we use the best-of-many Christoﬁdes algorithm on a special distribution of
trees. To obtain
we start with an optimal solution x∗ of the LP (1) and a distribution
P these trees,
∗
S
p with x = S∈S pS χ and round down the coeﬃcients to integer multiples of nǫ3 . By taking
multiple copies of trees, we will obtain trees S1 , . . . , Sr on which we can apply Theorem 4. Now,
there is a small contribution of trees that is lost due to the rounding error. We will deal with
these separately in the analysis and use that they can only represent a small fraction of x∗ . Bestof-many Christoﬁdes will then be applied to the union of the trees constructed by Theorem 4 (we
will call the set of these trees Ŝ) and the "leftover" trees. How exactly we deal with rounding will
be explained in the proof of Theorem 14.
Our goal is to choose for each tree S a cheap vector y S in the TS -join polyhedron to bound the cost
of parity correction for S. Clearly, y S = x∗ is a possible choice as x∗ (δ(U )) ≥ 1 for all ∅ =
6 U ⊂V.
But for the trees in Ŝ, we will construct better vectors.
10

We follow the analysis of Vygen [2015] (based on An, Kleinberg and Shmoys [2015] and Sebő
[2013]). Every tree S ∈ S can be partitioned into the edge set IS of the s-t-path in S and JS ,
which is a TS -join. For any narrow cut C ∈ C let eC ∈ C be a minimum cost edge in C. We will
choose numbers 0 ≤ β < 21 and 0 ≤ γS ≤ 1 for all S ∈ S later. Then, for S ∈ S, we set
z S :=

X

(1 − 2β)γS χ{e} +

e∈IS

X


max 0, (β(2 − x∗ (C) − ǫ) − (1 − 2β)γS ) χ{eC } .

(3)

C∈C : |S∩C| even

and
y S := β(1 + ǫ)x∗ + (1 − 2β)χJS + z S .

(4)

Observe that z S (C) ≥ β(2 − x∗ (C) − ǫ) for all C ∈ C with |S ∩ C| even. This implies that each
y S is in the TS -join polyhedron, because |δ(U ) ∩ S| even ⇔ |U ∩ TS | odd holds for all U ⊂ V with
|U ∩ {s, t}| = 1. We adapt Deﬁnition 6 and Lemma 7 of Vygen [2015] as follows.
Definition 11 Given numbers n
0 ≤ γS ≤ 1 foroS ∈ S and β < 12 , we define the beneﬁt of
∗ (C)−ǫ)
, γS if |S ∩ C| is even, bS,C := 1− γS if |S ∩ C| = 1,
(S, C) ∈ S × C to be bS,C := min β(2−x
1−2β
and bS,C = 0 otherwise.
1
2

Lemma P
12 Let 0 ≤ β <
and x = S∈S pS χS . If

X

S∈S

for all C ∈ C, then

P

S∈S

and 0 ≤ γS ≤ 1 for S ∈ S. Let p be an arbitrary distribution over S

pS bS,C ≥

P
β(2 − x∗ (C) − ǫ)( S∈S:|S∩C|even pS )
1 − 2β

(5)

pS c(y S ) ≤ (β + ǫβ)c(x∗ ) + (1 − 2β)c(x).

P
P
Proof: First we note that S∈S pS c(z S ) ≤ (1 − 2β) S∈S pS c(IS ) is proved exactly as in the
proof of Lemma 7 in Vygen [2015]. The claim then follows from
X

pS c(y S ) = β(1 + ǫ)c(x∗ ) + (1 − 2β)

S∈S

X

pS c(JS ) +

S∈S
∗

≤ β(1 + ǫ)c(x ) + (1 − 2β)

X

S∈S

X

pS c(z S )

S∈S

pS c(S).
✷

We now show how to set the γ-constants in order to maximize the beneﬁts, with the ultimate goal
to choose β as large as possible. Sebő [2013] set all γS to 21 . But we designed our r trees in such
a way that the trees with small indices have only one edge in narrow cuts, thus trees that have
an even number edges in a narrow cut tend to have larger indices. For example, for a narrow cut
11

C with x(C) = 32 , trees with index ≤ 2r have one edge in C (thus it is better to choose a smaller
γS for these). On the other hand, the trees that have an even number of edges in C will have an
index > r2 , and for those it is better to choose a bigger γS . Therefore we set γS = δ < 12 for the
ﬁrst half of the trees and γS = 1 − δ > 21 for the second half. More precisely:
P
Lemma 13 Let S1 , . . . , Sr ∈ S and ǫ ≥ 0 such that x = 1r rj=1 χSj satisfies (2), r is even, and
for every C ∈ C there exists an h ∈ {1, . . . , r} with hr ≥ 2 − x∗ (C) − ǫ and |C ∩ Sj | = 1 for all
j = 1, . . . , h.
We set δ := 0.126, and γSj = δ if j ≤ 2r and γSj = 1 − δ otherwise. Choose β such that
β
1−2β = 3.327. Then
1 Pr
1
∗
(6)
j=1 bSj ,Ci ≥ 3.327 (2 − x (Ci ) − ǫ) r |{j : |Sj ∩ Ci | even}|
r
for all i = 0, . . . , ℓ.

As the proof is quite technical, we prove this lemma in Section 4.
Using Lemma 12 and 13, we can show that the best-of-many Christoﬁdes algorithm run on the
trees constructed in Theorem 4 and the trees remaining after rounding is a 2−β +ǫ-approximation
for β as in Lemma 12 and obtain:
Theorem 14 There is a 1.566-approximation algorithm for the s-t-path TSP.
P
Proof: Let x∗ be an optimal solution for (1) and p a distribution over S with x∗ = S∈S pS χS
such that pS > 0 for at most n2 trees S. As mentioned before, x∗ and p canPbe found in
3
polynomial time. Setting p′S := nǫ3 ⌊ nǫ pS ⌋ and p′′S := pS − p′S for S ∈ S, we have S∈S p′′S ≤ nǫ
3 P
′
since |{S ∈ S : pS > 0}| ≤ n2 . By setting r = 2nǫ
S∈S pS (an even integer), we can obtain r
3
trees S1 , . .P
. , Sr , such that each S ∈ S appears 2⌊ nǫ pS ⌋ times in this list.
1
Let x = r rj=1 χSj . We show that x fulﬁlls property (2). Since all trees (V, S) with pS > 0 have
|δ(s) ∩ S| = |δ(t) ∩ S| = 1, we have x(δ(s)) = x(δ(t)) = 1. It remains to show x∗ (F ) − ǫ ≤ x(F ) ≤
x∗ (F ) + ǫ for all F ⊆ E:

X  p′
P S ′ − pS |S ∩ F |
x(F ) − x∗ (F ) =
p
S∈S

S∈S

S

P
′′
X pS − p′′ − (1 −
S
S∈S pS )pS
P
=
|S ∩ F |
1 − S∈S p′′S
S∈S
 |S ∩ F |
X
P
P
=
−p′′S + pS S∈S p′′S
1 − S∈S p′′S
S∈S


P
P
|S∩F |
P
Since |S∩F | ≤ |S| = n−1 for all S ∈ S, we have x(F )−x∗ (F ) ≤ ( S∈S p′′S )
S∈S (pS 1−
p′′ ) ≤
ǫ
(n−1)
n
1− nǫ

S∈S

≤ ǫ.

12

S

ǫ
P
(n−1)
|S∩F |
n
≥ −ǫ.
Similarly, x(F ) − x∗ (F ) ≥ − S∈S p′′S 1−P
′′ ≥ − 1− ǫ
p
S∈S S
n
This shows (2).
Using Theorem 4 we transform this list to Ŝ1 , . . . , Ŝr fulﬁlling the statement of the theorem.
β
= 3.327.
Therefore, we can apply Lemma 13 to Ŝ1 , . . . , Ŝr and x and obtain inequality (5) for 1−2β
Thus, we will be able to apply Lemma 12 in the analysis.
Our algorithm does parity correction for each of Ŝ1 , . . . , Ŝr and for all trees S with p′′S > 0 and
returns the best resulting tour. We obtain a bound on the value of the best output by an averaging
argument. For that, we use y Ŝj as deﬁned above in (4) to bound the parity correction cost for
trees Ŝj and x∗ for other trees.
P
P
P
′ S
We have x = 1r rj=1 χŜj = 1r rj=1 χSj = P 1 p′
S∈S pS χ . Therefore,
S∈S

c(x) = P

1

X

p′S c(S)
′
p
S∈S S S∈S

≤P

S

1

Then, using Lemma 12 in (∗) and (7) in (∗∗),

r

min min c(Ŝj ) + c(y Ŝj ) , min′′
j=1

≤

X

p′S

X

p′S c(S)

1
r

j=1

S∈S

=

S∈S:pS >0

r
X

S∈S

X

pS c(S)
′
S∈S pS S∈S

∗


c(S) + c(x )

=P

1

′
S∈S pS

c(x∗ ).

(7)



 P

c(Ŝj ) + c(y Ŝj ) + S∈S p′′S c(S) + c(x∗ )

+

X

p′S

S∈S

r
X

1
Sj
r c(y ) +

j=1

P

S∈S

r

X X
X 
1
Sj
p′S
= 1+
p′′S c(x∗ ) +
r c(y )

P

S∈S

p′′S c(x∗ )

j=1

S∈S

S∈S

p′′S c(S) +

X
X 
(∗) 

p′S (β + ǫβ)c(x∗ ) + (1 − 2β)c(x)
≤ 1+
p′′S c(x∗ ) +
S∈S

S∈S

(∗∗)

≤



1+

X

S∈S



p′′S c(x∗ ) +

X

p′S (β + ǫβ)c(x∗ ) + (1 − 2β)c(x∗ )

S∈S


X 
≤ 2 − β + ǫβ +
p′′S c(x∗ )
S∈S

< (2 − β + ǫ)c(x∗ ).

P
β
In the last inequality, we used S∈S p′′S ≤ nǫ . Moreover, 1−2β
= 3.327 is equivalent to β =
0.434 + 0.0006.
Thus, for ǫ ≤ 0.0006, our approximation ratio is at most 2 − 0.434 = 1.566.
13

3.327
7.654

>
✷

4

Computing the Benefit

In this section we prove Lemma 13.
Fix i ∈ {0, . . . , ℓ}. We write ξ := x∗ (Ci ) + ǫ, π := 1r |{j : |Sj ∩ Ci | even}|, and ρ := 1r θi −
(2 − x∗ (Ci ) − ǫ). That means ρr is the amount of θi due to rounding up (remember that θi =
⌈r(2 − x∗ (Ci ) − ǫ)⌉). We have π ≤ x(Ci ) − 1 ≤ x∗ (Ci ) + ǫ − 1 = ξ − 1: The ﬁrst inequality follows
from x(Ci ) ≥ 1r (|{Sj : |Ci ∩ Sj | ≥ 2}| + r) ≥ π + 1, the second is due to (2).
Clearly, (6) holds if π = 0 or ξ ≥ 2, thus we assume this is not true.
Suppose 3.327(2 − ξ) ≤ δ. Consequently, bSj ,Ci = β(2−ξ)
1−2β = 3.327(2 − ξ) for all j with |Sj ∩ Ci |
even. Thus, (6) trivially holds and we assume from now on 3.327(2 − ξ) > δ. For convenience of
notation, we deﬁne µ = min{1 − δ, 3.327(2 − ξ)}.
First note that among the trees Sj with j > θi , we either have trees with |Sj ∩ Ci | even or
additional trees with |Sj ∩ Ci | = 1, which will guarantee us a certain amount of beneﬁt: If there
is an f fraction of trees Sj with |Sj ∩ Ci | ≥ 3, then 3f + (1 − f ) + π ≤ x(Ci ) ≤ x∗ (Ci ) + ǫ = ξ, so
.
f ≤ ξ−π−1
2
Let us distinguish several cases.
Case 1: ξ ≤ 32 . Then θi ≥ 2r , and the ﬁrst half of the trees have only one edge in Ci .
We have 3.327(2 − ξ) ≥ 3.327 · 21 > 1 − δ. Therefore, µ = 1 − δ. Considering all trees, we obtain
the following lower bounds for the beneﬁt:
|Sj ∩ Ci |

j
r
2

j≤
r
2 < j ≤ θi
θi < j
θi < j
θi < j

fraction of trees

1
1
2,4,...
3,5,...
1

θi
r

−

1
2
1
3
=
2
2

−ξ+ρ

π
≤
− π − 1)
1
≥ 2 (ξ − π − 1) − ρ
1
2 (ξ

bSj ,Ci
1−δ
δ
µ
0
δ

Thus, we can bound the weighted beneﬁt (cf. Figure 4):
1 Pr
1−δ
3
1
j=1 bSj ,Ci ≥ 2 + ( 2 − ξ)δ + πµ + 2 (ξ − π − 1)δ
r
=

=

δ+1
2
δ+1
2

−
−

ξδ
2
ξδ
2

+ π(µ − 21 δ)

+ π(1 − 32 δ) =: g1 (ξ, π)).

14

1
1−δ
δ
0
0

1 θi
2 r

π

1

Figure 4: On the x-axis, we have the fraction of trees, on the y-axis their beneﬁt. A lower bound
for the beneﬁt for trees Sj is given by the grey area for j ≤ θi , the green (dotted) area for |Sj ∩ Ci |
even and the blue (lined) area otherwise.
To show (6), examine the minimum:


1 Pr
g1 (ξ, π)
j=1 bSj ,Ci
r
3
≥ min
: 1 ≤ ξ ≤ 2, 0 < π ≤ ξ − 1
π(2 − x∗ (Ci ) − ǫ)
π(2 − ξ)
)
(
ξδ
3
δ+1
−
+
(ξ
−
1)(1
−
δ)
(∗)
2
2
2
= min
: 1 ≤ ξ ≤ 32
(ξ − 1)(2 − ξ)
)
(
2δ − 12 + ξ(1 − 2δ)
: ξ ∈ R ≥ 3.327.
≥ min
(ξ − 1)(2 − ξ)
The ﬁrst inequality follows from the inequalities derived above. The equality (∗) follows by
ξδ 
∂ g1 (ξ,π)
1 δ+1
1
. This is
considering the partial derivative of the function in π: ∂π
2 − 2
π(2−ξ) = 2−ξ − π 2

g1 (ξ,π)
negative for all 1 ≤ ξ < 2 and δ < 1 and π > 0. Thus the minimum of π(2−ξ)
is attained at a
point where π is maximal and it suﬃces to consider the case where π = ξ − 1.
The last inequality is matter of computation: We just have to verify that 2δ − 12 + ξ(1 − 2δ) −
3.327(ξ − 1)(2 − ξ) ≥ 0 for δ = 0.126 and all ξ ∈ R. The minimum is attained at ξ ≈ 1.39.

Case 2: ξ > 32 . Then θi ≤ 2r because r is even. In this case, less than half of the trees are certain
to have only one edge on Ci .
Since bSj ,Ci = µ > δ for j ≥ 2r and |Sj ∩ Ci | even, in the worst case those indices j with |Sj ∩ Ci |
even are as small as possible. Thus, we obtain the following lower bounds:
j
j ≤ θi
θi < j ≤ min{ 2r , θi + rπ}
r
2 < j ≤ θi + rπ
θi < j
θi < j

|Sj ∩ Ci |

fraction of trees

bSj ,Ci

1
2,4,...
2,4,...
3,5,...
1

2−ξ+ρ
min{π, − 23 + ξ − ρ}
max{0, 32 − ξ + ρ + π}
≤ 12 (ξ − π − 1)
≥ 21 (ξ − π − 1) − ρ

1−δ
δ
µ
0
δ

15

1
1−δ
µ

π

δ
0
0

θi
r

1
2

1

Figure 5: On the x-axis, we have the fraction of trees, on the y-axis their beneﬁt. A lower bound
for the beneﬁt for trees Sj is given by the grey area for j ≤ θi , the green (dotted) area for |Sj ∩ Ci |
even and the blue (lined) area for the remaining trees.
Using the table we obtain (cf. Figure 5):
1 Pr
3
j=1 bSj ,Ci ≥ (2 − ξ + ρ)(1 − δ) + min{π, − 2 + ξ − ρ}δ
r

+ max{0, 32 − ξ + ρ + π}µ + ( 21 (ξ − π − 1) − ρ)δ

≥ (2 − ξ)(1 − δ) + min{π, − 32 + ξ}δ + max{0, 32 − ξ + π}µ + 12 (ξ − π − 1)δ
+ ρ(1 − 2δ)
≥ (2 − ξ)(1 − δ) + min{π, − 23 + ξ}δ + max{0, 32 − ξ + π}µ + 12 (ξ − π − 1)δ
=: g2 (ξ, π).
Now, we distinguish two cases, depending on where the minimum in g2 is attained.
Case 2.1: π ≤ ξ − 23 . Then g2 (ξ, π) = (2 − ξ)(1 − δ) + πδ + 2δ (ξ − π − 1) = 2 − 25 δ + ( 23 δ − 1)ξ + 2δ π.
As before, we minimize


1 Pr
g2 (ξ, π) 3
j=1 bSj ,Ci
r
3
≥ min
: < ξ < 2, 0 < π ≤ ξ − 2
π(2 − x∗ (Ci ) − ǫ)
π(2 − ξ) 2
)
(
2 − 52 δ + ( 32 δ − 1)ξ + δ2 (ξ − 32 ) 3
(∗)
: 2 <ξ<2
= min
(ξ − 32 )(2 − ξ)
(
)
2 − 13
4 δ + (2δ − 1)ξ
≥ min
: ξ ∈ R ≥ 3.327
(ξ − 32 )(2 − ξ)
1
∂ g2 (ξ,π)
To show (∗), as before, we consider the partial derivative in π and obtain ∂π
π(2−ξ) = 2−ξ −

1
∂ g2 (ξ,π)
2 − 52 δ + ( 32 δ − 1)ξ . Since 2 − 25 δ + ( 32 δ − 1)ξ = (2 − ξ)(1 − 23 δ) + 2δ > 0, we have ∂π
π(2−ξ) < 0
π2

for all ξ < 2 and π > 0, and the minimum is attained for π = ξ − 23 . To verify the last inequality,
3
checking 2− 13
4 δ + (2δ − 1)ξ − 3.327(ξ − 2 )(2− ξ) ≥ 0 for δ = 0.126 and all ξ ∈ R is straightforward.
(The minimum is attained at ξ ≈ 1.86.)
16

Case 2.2: π > ξ − 32 . Then g2 (ξ, π) = (2 − ξ)(1 − δ) + (ξ − 23 )δ + ( 23 − ξ + π)µ + 12 (ξ − π − 1)δ =
2 − 4δ + 23 µ + ξ( 52 δ − 1 − µ) + π(µ − 12 δ).
Minimization yields
1 Pr
j=1 bSj ,Ci
r
π(2 − x∗ (Ci ) − ǫ)


g2 (ξ, π) 3
3
≥ min
: < ξ < 2, ξ − 2 ≤ π ≤ ξ − 1
π(2 − ξ) 2
(
2 − 4δ + 32 µ + ξ( 25 δ − 1 − µ) + π(µ − 12 δ)
(∗)
= min
:
π(2 − ξ)

3
2

)

< ξ < 2, π ∈ {ξ − 32 , ξ − 1}

(∗∗)

≥ 3.327.

1
1
∂ g2 (ξ,π)
3
To show (∗), again consider the partial derivative in π: ∂π
π(2−ξ) = 2−ξ − π 2 2 − 4δ + 2 µ +

ξ( 25 δ − 1 − µ) . Unlike the previous cases, this function can be positive or negative for δ = 0.126
and 32 < ξ < 2 and π > 0. But for ﬁxed ξ, it is either always non-negative or always nonpositive. Therefore the minimum is either attained for maximal or for minimal π, which explains
the equality.
We now show (∗∗). Let us examine the two possible choices for π. For π = ξ − 32 , we minimize
g2 (ξ,ξ− 23 )
,
(ξ− 32 )(2−ξ)

which is the same function as in Case 2.1 (note that the terms involving µ cancel).

For π = ξ − 1, we get:
(

2 − 4δ + 32 µ + ξ( 25 δ − 1 − µ) + (ξ − 1)(µ − 12 δ)
:
min
(ξ − 1)(2 − ξ)
)
(
2 − 72 δ + 12 µ + ξ(2δ − 1)
:ξ∈R .
≥ min
(ξ − 1)(2 − ξ)

If µ = 1 − δ, (8) equals min
ξ∈R

n5
2

−4δ+ξ(2δ−1)
(ξ−1)(2−ξ)

o

= min
ξ∈R

n

2δ− 12 +(3−ξ)(1−2δ)
(ξ−1)(2−ξ)

o

3
2

)

<ξ<2

(8)
= min
′
ξ ∈R

n

2δ− 12 +ξ ′ (1−2δ)
(ξ ′ −1)(2−ξ ′ )

o

.

We replaced ξ ′ = 3 − ξ, which corresponds to mirroring at 23 . This minimum was already shown
to be at least 3.327 in Case 1.
If µ = 3.327(2 − ξ), then (8) is equal to
(
)
2 − 27 δ + ξ(2δ − 1) + 12 3.327(2 − ξ) 3
min
: 2 <ξ<2 .
(ξ − 1)(2 − ξ)
To see that this is at least 3.327, it just remains to check that 2 − 27 δ + ξ(2δ − 1) + 21 3.327(2 −
ξ) − 3.327(ξ − 1)(2 − ξ) ≥ 0 for δ = 0.126 and all ξ ∈ R. The minimum is attained at ξ ≈ 1.86.
This completes the proof of Lemma 13.
17

5

Conclusion

The approximation ratio can probably be improved slightly by choosing the γŜj diﬀerently, but
still depending only on rj . However, using an analysis based on Lemma 12, one cannot obtain a
because the beneﬁt can never be more than one and there can
better approximation ratio than 14
P9
β
3
∗
be cuts C with x (C) = 2 and S∈S:|S∩C| even pS = 12 ; therefore 1−2β
≤ 4. Our ratio is already
close to this threshold.
On the other hand, it is not impossible that the best-of-many Christoﬁdes algorithm on a distribution like the one obtained in Theorem 4, or even on an arbitrary distribution, has a better
approximation ratio, maybe even 23 .

References
An, H.-C., Kleinberg, R., and Shmoys, D.B. [2015]: Improving Christoﬁdes’ algorithm for the s-t path
TSP. Journal of the ACM 62 (2015), Article 34
Asadpour, A., Goemans, M.X., Mądry, A., Oveis Gharan, S., and Saberi, A. [2010]: An O(log n/ log log n)approximation algorithm for the asymmetric traveling salesman problem. Proceedings of the 21st Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), 379–389
Christoﬁdes, N. [1976]: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical
Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh 1976
Dantzig, G.B., Fulkerson, D.R., and Johnson, S.M. [1954]: Solution of a large scale traveling salesman
problem. Operations Research 2 (1954), 393–410
Edmonds, J. [1965]: The Chinese postman’s problem. Bulletin of the Operations Research Society of
America 13 (1965), B-73
Edmonds, J., and Johnson, E.L. [1973]: Matching, Euler tours and the Chinese postman. Mathematical
Programming 5 (1973), 88–124
Gao, Z. [2013]: An LP-based 23 -approximation algorithm for the s-t path graph traveling salesman problem.
Operations Research Letters 41 (2013), 615–617
Gao, Z. [2015]: On the metric s-t path traveling salesman problem. SIAM Journal on Discrete Mathematics
29 (2015), 1133–1149
Genova, K., and Williamson, D.P. [2015]: An experimental evaluation of the best-of-many Christoﬁdes’
algorithm for the traveling salesman problem. arXiv:1506.07776 (extended abstract to appear in ESA
2015)
Grötschel, M., Lovász, L., and Schrijver, A. [1981]: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 (1981), 169–197
Held, M., and Karp, R.M. [1970]: The traveling-salesman problem and minimum spanning trees. Operations Research 18 (1970), 1138–1162

18

Hoogeveen, J.A. [1991]: Analysis of Christoﬁdes’ heuristic: some paths are more diﬃcult than cycles.
Operations Research Letters 10 (1991), 291–295
Oveis Gharan, S., Saberi, A., and Singh, M. [2011]: A randomized rounding approach to the traveling
salesman problem. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer
Science (FOCS 2011), 550–559
Sebő, A. [2013]: Eight ﬁfth approximation for TSP paths. In: Integer Programming and Combinatorial
Optimization; Proceedings of the 16th IPCO Conference; LNCS 7801 (J. Correa, M.X. Goemans, eds.),
Springer 2013, pp. 362–374
Sebő, A., and Vygen, J. [2014]: Shorter tours by nicer ears: 7/5-approximation for graph-TSP, 3/2 for the
path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34 (2014), 597–629
Vygen, J. [2012]: New approximation algorithms for the TSP. OPTIMA 90 (2012), 1–12
Vygen, J. [2015]: Reassembling trees for the traveling salesman. arXiv:1502.03715

19

