The Salesman's Improved Paths: \\$3/2+1/34$ Integrality Gap and Approximation Ratio \thanks{Research initiated during the Hausdorff Trimester Program in Combinatorial Optimization, Hausdorff Institute of Mathematics, Bonn; Partially supported by LabEx PERSYVAL-Lab (ANR 11-LABX-0025) and by a grant from the Simons Foundation (\#359525, Anke Van Zuylen).
We give a new, strongly polynomial algorithm and improved analysis of the metric $s-t$ path TSP. The algorithm finds a tour of cost less than $1.53$ times the optimum of the subtour elimination LP, while known examples show that $1.5$ is a lower bound for the integrality gap. A key new idea is the deletion of some edges, where the arising connectivity problems can be solved for a minor extra cost. On the one hand our algorithm and analysis extend previous tools, at the same time simplifying the framework. On the other hand new tools are introduced, such as a linear program that allows us to efficiently choose the probabilities of edges used for analyzing the reconnection cost and a new way of applying the matroid partition theorem and algorithm to different matroids, in order to write the subtour elimination optimum as a particular convex combination of spanning trees. Furthermore, the $3/2$ target-bound is easily reached in some relevant new cases. %\thispagestyle{empty \smallskip\noindent \noindent{\footnotesize {keywords: path traveling salesman problem (TSP), approximation algorithm, Christofides' heuristic, the Chinese postman problem, matching theory, $T$-join, polyhedra
1604.02486.tex
\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{authblk}
\usepackage[hidelinks]{hyperref}
\usepackage{enumitem}
\usepackage[longend,noresetcount,boxed]{algorithm2e}
\usepackage{tikz}
\usetikzlibrary{positioning}
\usepackage{xcolor}
\usepackage{colortbl}
\usepackage{ifthen}
\usepackage{soul}




\usepackage{anysize}
\usepackage{microtype}
\marginsize{1in}{1in}{1in}{1in}
\setlength{\textwidth}{6.5in} % set width of text portion
\pdfpagewidth 8.5in
\pdfpageheight 11.0in



\begin{document}
\DontPrintSemicolon
\LinesNotNumbered
\SetAlCapSkip{8pt}
\def\qed{\hfill$\Box$}
\def\Nset{\mathbb{N}}
\def\Ascr{\mathcal{A}}
\def\Bscr{\mathcal{B}}
\def\Cscr{\mathcal{C}}
\def\Dscr{\mathcal{D}}
\def\Escr{\mathcal{E}}
\def\Fscr{\mathcal{F}}
\def\Hscr{\mathcal{H}}
\def\Iscr{\mathcal{I}}
\def\Jscr{\mathcal{J}}
\def\Mscr{\mathcal{M}}
\def\Nscr{\mathcal{N}}
\def\Pscr{\mathcal{P}}
\def\Qscr{\mathcal{Q}}
\def\Rscr{\mathcal{R}}
\def\Sscr{\mathcal{S}}
\def\Wscr{\mathcal{W}}
\def\Xscr{\mathcal{X}}
\def\cupp{\stackrel{.}{\cup}}
\def\bold{\bf\boldmath}


\newcommand{\NP}{\mbox{\slshape NP}}
\newcommand{\opt}{\mbox{\scriptsize\rm OPT}}
\newcommand{\lin}{\mbox{\scriptsize\rm $OPT_{LP}$}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}{Claim}

\def\prove{\par \noindent \hbox{{\bf Proof}:}\quad}
\def\endproof{\eol \rightline{$\Box$} \par}
\renewcommand{\endproof}{\hspace*{\fill} {\boldmath $\Box$} \par \vskip0.5em}
\newcommand{\mathendproof}{\vskip-1.8em\hspace*{\fill} {\boldmath $\Box$} \par \vskip1.8em}
\newcommand{\E}[1]{\mathbb{E}\left[#1\right]}


\setlist[itemize]{leftmargin=0pt}
\setlist[enumerate]{leftmargin=15pt}


\title {The Salesman's Improved Paths:  \\$3/2+1/34$ Integrality Gap and Approximation Ratio \thanks{Research initiated during the  Hausdorff Trimester Program in Combinatorial Optimization, Hausdorff Institute of Mathematics, Bonn; Partially supported by LabEx PERSYVAL-Lab (ANR 11-LABX-0025) and by a grant from the Simons Foundation (\#359525, Anke Van Zuylen). }}
\author[1]{Andr\'as Seb\H{o}}
\author[2]{Anke van Zuylen}
\affil[1]{\small CNRS, Univ. Grenoble Alpes,  Optimisation Combinatoire (G-SCOP) %\url{Andras.Sebo@grenoble-inp.fr}
	}
\affil[2]{\small Department of Mathematics\\ College of William \& Mary\\ Williamsburg, VA\\ \url{anke@wm.edu} }

\maketitle


\begin{abstract}
We give a new, strongly polynomial algorithm and improved analysis of the metric $s-t$ path TSP. The algorithm finds a tour of cost  less than $1.53$ times the optimum of the subtour elimination LP,  while known examples show that $1.5$ is a lower bound for the integrality gap.

A key new idea is the deletion of some edges, where the arising connectivity problems can be solved for a minor extra cost. On the one hand our algorithm and analysis  extend previous tools, at the same time simplifying the framework.  On the other hand new tools are introduced, such as a linear program that allows us to efficiently choose the probabilities of edges used for analyzing the reconnection cost and a new way of applying the matroid partition theorem and algorithm to different matroids, in order to write the subtour elimination optimum as a particular  convex combination of spanning trees. 

Furthermore, the $3/2$ target-bound is easily reached in some relevant new cases. 

%\thispagestyle{empty}
\smallskip\noindent
\noindent{\footnotesize {\bf keywords}: path traveling salesman problem (TSP),
approximation algorithm, Christofides' heuristic, the Chinese postman problem, matching theory, $T$-join, polyhedra}
\end{abstract}

% \clearpage
% \setcounter{page}{1}

\section{Introduction}\label{sec:i}
In the Traveling Salesman Problem (TSP), we are given a set $V$ of $n$ ``cities'', a cost function $c: {V\choose 2}\to \mathbb{Q}^{\ge0}$, and the goal is to find a tour of minimum cost that starts and ends in the same city and visits each city exactly once. This ``minimum length Hamiltonian circuit'' problem is one of the most well-known problems of combinatorial optimization. In its full generality, the TSP is hopeless: it is not only \NP-hard to solve but also to approximate, and even for quite particular lengths, since  the Hamiltonian cycle problem in $3$-regular graphs is \NP-hard \cite{GarJT76}.

A condition on the cost function that helps in theory and is often satisfied in practice is known as the ``triangle inequality'' in complete graphs. A nonnegative function on the edges that satisfies this inequality is called a {\em metric} function. For a thoughtful and entertaining account of the difficulties and successes of the TSP, see Bill Cook's book \cite{Cook11}. 

If the cost function is a metric, then we may relax the problem into finding a Eulerian  sub-multigraph $(V, E^*)$ of minimum cost $\sum_{e\in E^*} c(e)$, since a traversal of this graph  can be shortcut to a tour without increasing the cost. The multiplicities of edges can be restricted to be $0$, $1$ or $2$.

Christofides~\cite{Christofides76} gave a very simple $\frac32$-approximation algorithm for the metric TSP:
separate the problem into finding a minimum cost connected subgraph (minimum cost spanning tree) and  completing this tree to an Eulerian subgraph, by correcting the parity of the constructed tree, $S$, i.e., by adding a minimum cost $T_S$-join, where $T_S$ is the set of vertices that have odd degree in $S$ (Chinese postman problem). Wolsey~\cite{Wolsey80} observed that Christofides' algorithm also implies a bound on the strength of the well-known subtour elimination linear program (LP), that was introduced by Dantzig, Fulkerson and Johnson \cite{DantzigFJ54}:
\begin{eqnarray}
& \mbox{Min} & c(x):= \sum_{e \in {V\choose 2}} c(e) x(e) \nonumber\\
 & \mbox{subject to:} &  \sum_{e \in \delta(\{i\})} x(e) = f(\{i\}), \ \  \hbox{ for all } i \in V, \label{degreecons} \\
& &  \sum_{e \in \delta(U)}x(e) \geq f(U), \ \  \hbox{ for all } \emptyset \subsetneq U\subsetneq V,\, \label{subtourcons}\\
& & x(e) \geq 0, \ \ \ \hbox{ for all } e \in {V\choose 2}. \label{boundscons}
\end{eqnarray}
where $f(U)\equiv 2$ for all sets $U$, and $\delta(U)=\{\{i,j\}\in E:i\in U, j\not\in U\}$. The first set of constraints impose the condition that every vertex is visited once, and the second set of constraints, known as the subtour elimination constraints, ensure that every subset is visited at least once. Let $x^*$ denote an optimal solution to the subtour elimination LP, and $\lin:=\lin(c):=c(x^*)$ the optimal objective value.
The integrality gap for metric TSP is the worst-case ratio, over all metric cost functions, of the cost of the optimal tour to $\lin$. 
Wolsey~\cite{Wolsey80} observed that 
$x^*$ is in the the spanning tree polytope, and that $x^*/2$ is in the $T$-join polyhedron for any set $T$ of even size, which implies that the integrality gap of the subtour elimination LP is at most $\frac32$.

Despite significant effort, no improvements are known for either the approximation ratio or the integrality gap for the metric TSP.

A relevant generalization of the (metric) TSP is the (metric) $s-t$ path TSP. In this problem, the salesman starts in $s$,  ends in $t$, and needs to visit every other city once. In other words, the goal is to find a Hamiltonian path from $s$ to $t$ of minimum cost. The subtour elimination LP for the $s-t$ path TSP is as above, but now defining $f(U)=1$ if $|U\cap \{s,t\}|=1$ and $f(U)=2$ otherwise. Note that the special case $s=t$  is the regular traveling salesman problem.

\smallskip
In this paper, we describe a new,  combinatorial, strongly polynomial algorithm and improved analysis with the new approximation and integrality ratio $3/2+1/34$ for the metric $s-t$ path traveling salesman problem. To achieve this, we also need {\em to delete edges from Christofides' trees}, in the hope that they will be automatically reconnected during parity correction; however, this is not always the case, and whenever it is not, we also need to invest separately in {\em reconnection}; for analyzing it, we use an LP for defining the distribution of a random choice for the reconnecting edges, we explore a new way of using matroid partition for finding the initial set of trees, and we consider a specific convex combination of $T$-joins rather than a minimum cost $T$-join. 
	
\medskip
To the best of our knowledge, the first relevant occurrence of possibly different $s$ and $t$ is 
in Hoogeveen's article \cite{Hoogeveen91}, providing a Christofides-type approximation algorithm for the metric case, with an approximation ratio of $5/3$ rather than $3/2$. There had been no improvement until An, Kleinberg and Shmoys \cite{AnKS12,AnKS12bis}  improved this ratio to $\frac{1+\sqrt{5}}{2}<1.618034$ with a simple algorithm and an ingenious new framework for the analysis.
The algorithm in \cite{AnKS12,AnKS12bis} is the {\em best-of-many}  version of Christofides' algorithm. It first determines a minimum cost solution $x^*$ of the subtour elimination LP.  Then  writing $x^*$ as a convex combination of spanning trees and adding  Christofides' {\em parity correction} for each, the algorithm outputs the best of the arising solutions. The best-of-many algorithm was used by subsequent publications and is also used in the present work with some modification; mainly, we alter Christofides' algorithm by deleting certain edges from the spanning tree (see Section~\ref{sub:BOM}), and by then correcting both parity and connectivity.

To analyze the best-of-many algorithm, An, Kleinberg and Shmoys~\cite{AnKS12} come up with a certain ``master formula'' to bound the average parity correction cost, that was also used in subsequent publications. Seb\H{o} \cite{Sebo13} improved the analysis further by separating each spanning tree in the convex combination into an $s-t$ path and its complement. Letting $p^*$ be the indicator vector of the average of the $s-t$ paths, and $q^*$ of the edges that are not on the $s-t$ path, we have that $x^*=p^*+q^*$.  This separation makes it possible to use a simple and transparent master formula (see (\ref{eq:BPC}) in Section~\ref{sub:co}), but, surprisingly, until now the original, quite involved one was used by all the papers on $s-t$ path TSP following~\cite{AnKS12}.  Moreover, $p^*$ is further decomposed: it is the sum of naturally arising vectors (see $x^Q$ later on). These vectors are getting an extended role in the present paper (Section~\ref{sub:co}). 

For the $s-t$ path TSP on ``graph metrics'', that is, cost functions that are defined as the shortest path distances on a given unweighted graph, Gao~\cite{Gao13}  proves the existence of a tree in the support of LP solution $x^*$ that has exactly one edge in so-called narrow cuts (see Section~\ref{sub:BOM} below). For such a tree, it is possible to bound the cost of the parity correction by $c(x^*)/2$, as in Wolsey's  version of Christofides' analysis. This allows Gao to give  a very elegant proof of the approximation ratio $3/2$ for graph metrics, a result that was first shown by \cite{SV} with a combinatorial, but more difficult proof.

Recently, Gottschalk and Vygen \cite{GottschalkV15} significantly extended Gao's approach by proving the existence of a decomposition of $x^*$ into certain ``layers''; each layer consists of spanning trees that have exactly one edge in a subset of the narrow cuts.  This will turn out to be needed in our analysis. 
We show that it  is actually a {\em particular matroid partition}, which is also algorithmically useful  for a strongly polynomial combinatorial algorithm (see Section~\ref{sub:Gao} and Section~\ref{sec:decomp}).  However, the constraints of the corresponding matroid partition (or basis packing) theorem of Edmonds \cite{Edm65} are apparently not straightforward to prove (see Appendix~\ref{sec:matroids} for a weaker statement and the exposition of the problem); we therefore make use for the moment of \cite{GottschalkV15} for checking the validity of Edmonds' matroid  partition  condition. The occurring particular matroid sums will probably remain a  helpful  tool for the s-t-path TSP problem, and we believe  that a direct way of proving Edmonds' condition will eventually be found.



In the next section, we provide more details for the approaches described above in the form we need them in this paper, along with the novel algorithm and tools of our analysis. 


\section{Preliminaries, Algorithm and Outline of the Analysis}\label{sec:BOM}
In this section we introduce our notation, terminology, and definitions. In the first subsection we also state our new algorithm. The second subsection gives an overview of the ideas we need to analyze our algorithm. The third subsection explains a particular phenomenon of the algorithm and its analysis: the necessity to choose  a particular convex combination of trees.

\subsection{The Algorithm: Best-of-Many with Deletion}\label{sub:BOM}
Given a finite set $V$ and costs $c:{V \choose 2}\to \mathbb{Q}_{\ge 0}$ satisfying the triangle inequality,  let  $x^*$ be the  minimum cost solution to the subtour elimination LP for $s-t$ path TSP, and $E=\{e: x^*(e)>0\}$. We will slightly abuse notation, and use the same notation for a (multi) subset of $E$ and its own incidence vector in $\mathbb{Z}_{\ge 0}^E$.  For a vector $z\in \mathbb{R}^E$ and any (multi)subset $H$ of $E$, the usual notation $z(H):=\sum_{e\in H} z(e)$ is then just the scalar product of two vectors, as well as $c(z):=\sum_{e\in E}c(e)z(e)$. 


We can write $x^*$ as a convex combination of spanning trees; that is, there exist a collection of spanning trees $\Sscr$ and coefficients $\lambda_S>0$ for $S\in \Sscr$ such that $\sum_{S\in \Sscr} \lambda_S=1$ and $x^*=\sum_{S\in \Sscr} \lambda_S S$, and these can be found in strongly polynomial time with a combinatorial algorithm.  (The existence follows from Tutte and Nash-Williams' theorems \cite{Tutte61}, \cite{NW61}; the combinatorial algorithm from Cunningham~\cite{Cunningham84}; see also Barahona~\cite{Barahona95} for a result specifically concerning spanning trees, and Schrijver~\cite[page 891]{Schrijver-book} for an account of the best complexities so far.)

For a set of edges $S$, we let $T_S$ be the set of odd degree vertices of $S$, i.e. those that have an odd number of incident edges from $S$. For two sets $A$, $B$, let $A\triangle B:=(A\setminus B) \cup (B\setminus A)$ be the {\em symmetric difference} operation, which corresponds to the mod~$2$ sum of the incidence vectors. Then the vertex set  with the ``wrong'' degree parity is $T_S\triangle \{s,t\}$.  A $T$-join $(T\subseteq V,\,\hbox{$|T|$ is even})$ is a set of edges $J$ such that $|J\cap \delta(\{i\})|$ is odd for $i\in T$ and $|J\cap \delta(\{i\})|$ is even for $i\in V\setminus T$.
The operation ``$+$'' between sets means the disjoint union (sum of the multiplicity vectors).  If $S$ is a spanning tree and $J_S$ a $T_S\triangle\{s,t\}$-join,  $(V,S+J_S)$ is a spanning connected multigraph in which $s$ and $t$ have odd degree and every other vertex has even degree. We call the edge set of such a graph an $\{s,t\}$-tour.

The best-of-many Christofides' (BOMC) algorithm computes a minimum cost $T_S\triangle \{s,t\}$-join for every tree $S$ with $\lambda_S>0$, and outputs the resulting $\{s,t\}$-tour of minimum total cost. The cost of the BOMC solution is at most the cost of the $\{s,t\}$-tour we obtain by adding a  $T_{\Sscr}\triangle\{s,t\}$-join to a randomly chosen spanning tree $\Sscr$ with $\Pr(\Sscr=S)=\lambda_S$. Clearly, the expected cost of $\Sscr$ is equal to $c(x^*)$; the main difficulty for the analysis of the s-t path TSP version of Christofides' algorithm is the ``parity correction'' part.  It follows from Edmonds and Johnson~\cite{EdmJ73} that the $T_S\triangle \{s,t\}$-join polyhedron is
\vspace{-\baselineskip}
\begin{eqnarray*}
&&\sum_{e\in \delta(U)}y(e)\ge 1\mbox{ for all $U$ such that $|U\cap T_S\triangle \{s,t\}|$ is odd},\label{oddcuts}\\
&& y(e) \ge 0 \mbox{ for all }e\in E.
\end{eqnarray*}
As  noted above, Wolsey~\cite{Wolsey80} observed for the TSP (i.e. for  $s=t$) and a solution $x^*$ to the subtour elimination LP for the TSP that $x^*/2$ is in the $T$-join polyhedron for any set  $ T\subseteq V,\,\hbox{$|T|$  even}$.  If $s\neq t$ this is not true anymore for a solution  $x^*$  to the corresponding subtour elimination LP since for cuts $U$ separating $s$ and $t$, called {\em $s-t$ cuts}, $f(U)=1$ in the LP, and hence we are only guaranteed that $x^*(\delta(U))/2\ge \frac12$.

Following~\cite{AnKS12,AnKS12bis},  we say that $Q\subset E$ is {\em narrow} if $x^*(Q) < 2$. We let ${\cal Q}$ be the set of all narrow cuts, that is, ${\cal Q}=\{Q\subset E: x^*(Q)<2\}$.  Figure~\ref{fig:Gao} shows an example of an optimal solution $x^*$ to the subtour elimination LP for an $s-t$ path TSP and the narrow cuts $\Qscr$. An, Kleinberg and Shmoys~\cite{AnKS12,AnKS12bis}, observe that  ${\cal Q}$ is a chain:
\begin{lemma}[An, Kleinberg, Shmoys~\cite{AnKS12,AnKS12bis}]\label{lem:chain}
Let $U_1, U_2$ such that $s\in U_1\cap U_2$, and $Q_i=\delta(U_i)$ is in $\Qscr$ for $i=1,2$. Then either $U_1\subseteq U_2$, or
$U_2\subseteq U_1$.
\end{lemma}

\begin{figure}
\begin{center}
\begin{tikzpicture}[->,shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,draw,font=\sffamily\bfseries\scriptsize},aux node/.style={}]

 
  \node[main node] (0) {$s$};
  


 \foreach \name/\pos in {{1/0}, {2/1}, {4/2}, {5/4}, {6/5}, {t/6}}
   \node[main node] (\name) [right of = \pos] {$\name$};

  \foreach \name/\pos in {{Q_1/0},{Q_2/1},{Q_3/2},{Q_4/4},{Q_5/5},{Q_6/6}}
   \node[aux node] (\name) [above right = 1.5cm and 0.1cm of \pos] {$\name$};

  \foreach \name/\pos in {{P_1/0},{P_2/1},{P_3/2},{P_4/4},{P_5/5},{P_6/6}}
   \node[aux node] (\name) [below right = 1.5cm and 0.1cm of \pos] {};


  \foreach \name/\pos in {{3/4}}
   \node[main node] (\name) [above of = \pos] {$\name$};
    
 \path[-,every node/.style={font=\sffamily}]
 	\foreach \source/\dest in {0/1,4/5,6/t}{
 		(\source) edge [very thick, dashed] node {} (\dest)	}
	\foreach \source/\dest in {0/3,1/3,5/2,t/2,3/6}{
		(\source) edge [dotted, bend left] node {} (\dest)	} 			
	(2) edge [dotted] node {} (4)	 			
	\foreach \source/ \dest in {1/2,5/6,3/4} {
		(\source) edge [very thick] node  {} (\dest)
	}
	\foreach \source /\dest in {Q_1/P_1,Q_2/P_2,Q_3/P_3,Q_4/P_4,Q_5/P_5,Q_6/P_6}{
		(\source) edge [very thick,gray!35] node  {} (\dest)
	}
;
\end{tikzpicture}
\end{center}
\vspace{-2\baselineskip}
\caption{An example from Gao~\cite{Gao15}: for full edges $x^*(e)=1$, for dashed edges $x^*(e)=2/3$ and for dotted edges  $x^*(e)=1/3$. The narrow cuts are indicated by gray lines and labeled $Q_1,\ldots, Q_6$.} \label{fig:Gao}
\end{figure}


We include a brief proof (with some useful elements for the more general Lemma~\ref{lem:disGao}): 

\medskip
\prove
The lemma is a consequence of the submodular inequality that will be helpful in the following equality form: 
\begin{equation}
x^*(\delta (A)) + x^*(\delta (B))= x^*(\delta (A\cap B))+ x^*(\delta (A\cup B)) + 2 x^*(A\setminus B, B\setminus A),\label{eq:submodularity}
\end{equation}
where $(X,Y)$ is the set of edges with one endpoint in $X$, the other in $Y$. The equality is easily verified.
Now to show Lemma~\ref{lem:chain} apply (\ref{eq:submodularity}) to $A:=U_1$, $B:=V\setminus U_2$.
If the lemma does not hold, $A\cap B$ and $A\cup B$ are both non-empty, strict subsets of $V$. Furthermore, note that $A\cap B$ contains neither of $s,t$ and $A\cup B$ contains both of $s,t$. Hence, by constraint~(\ref{subtourcons}), the first and second terms in the right hand side of~(\ref{eq:submodularity}) are at least $2$, contradicting that the left hand side is strictly smaller than $4$ since $\delta(U_1), \delta(U_2)\in \Qscr$.
\qed
\medskip

An, Kleinberg and Shmoys~\cite{AnKS12,AnKS12bis}  observe that for a narrow cut $Q=\delta(U)$, the $T_S\triangle \{s,t\}$-join polyhedron has a constraint for $U$ only if the spanning tree $S$ has an even number of edges in $Q$. In Section~\ref{sub:co}, we  give all necessary details of their approach and later works~\cite{Sebo13,Gao15,Vygen15,GottschalkV15} on analyzing the cost of the $T_S\triangle \{s,t\}$-join for $S\in \Sscr$.


\begin{algorithm}[!h]
\caption{Best-of-Many With Deletion (BOMD)}\label{alg:bomd}
{INPUT: Set $V$, two vertices, $s,t\in V$ and $c: {V\choose 2}\to \mathbb{Q}^{\ge0}$.

OUTPUT: An $\{s,t\}$-tour.


Let $x^*$ be an optimal solution to the subtour elimination LP for the $s-t$ path TSP,
and write $x^*$ as a layered convex combination of  $O(|E|)$ spanning trees (see the definition in Section~\ref{sub:Gao}, and a proof of existence in Section~\ref{sec:decomp}).\;
Let $\Sscr$ be the collection of trees with positive coefficient.\;
\For{$S\in \Sscr$}
{
	{\bf Construct forest-based $\{s,t\}$-tour:}\;
	Let $L(S)$ be the set of lonely edges of $S$, and $F:=F(S):=S\setminus L(S)$.\;
	Let $y_F$ be the vector in the $T_F\triangle \{s,t\}$-join polyhedron defined in  Section~\ref{sec:ratio}. \;
	Write $y_F$ as a convex combination of at most $O(|E|)$  different $T_F\triangle \{s,t\}$-joins. Let $\Jscr_F$ be the collection of $T_F\triangle \{s,t\}$-joins with positive coefficient.\;
	\For{$J_F\in \Jscr_F$}
	{
		Contract the components of $(V, F+J_F)$, and let $2D_{F+J_F}$ be the edge set of a doubled minimum cost spanning tree on the contracted graph.\;
		$P_{1}(F,J_F)=F+J_F+2D_{F+J_F}$.\;
	}
	Let $P_1(S)$ be a minimum cost $\{s,t\}$-tour among $\{P_1(F, J_F)\}_{J_F\in\Jscr_F}$.\;
	{\bf Construct Christofides-based $\{s,t\}$-tour:}\;
	$P_{2}(S)=S+J_S$, where $J_S$ is a minimum cost $T_S\triangle \{s,t\}$-join.\;
}
Return a minimum cost $\{s,t\}$-tour from among  $\bigcup_{S\in \Sscr}\{P_1(S), P_2(S)\}$. 
}
\end{algorithm}

	In this paper, we modify the best-of-many Christofides' algorithm by {\em deleting} certain edges  called {\em lonely} from the spanning trees $S\in \Sscr$.  We denote by $L(S)$ the set of lonely edges of tree $S$, where we require for all $e\in L(S)$ that the two components of $S\setminus\{e\}$ are  the two sides of a narrow cut, that is, 
	\begin{equation}
	 L(S)\subseteq \big\{e\in S: \hbox{there exists $Q\in\Qscr$ such that } Q\cap S=\{e\} \big\}.
	 \label{eq:lonelysubset}
	\end{equation}
	Note that we do not require equality in (\ref{eq:lonelysubset}), and this flexibility will enable us to choose the lonely edges to satisfy additional conditions.
	For each tree $S\in \Sscr$, we delete its lonely edges to obtain a forest $F(S):=S\setminus L(S)$. We  write $F$ instead of $F(S)$ whenever $S$ is clear from the context. We then add a $T_F\triangle \{s,t\}$-join to obtain a graph in which each vertex except for $s$ and $t$ has even degree, and finally, we add a doubled spanning tree on the components of this graph to get an $\{s,t\}$-tour. Note that adding a spanning tree on the components suffices to make the graph connected, and we double it in order to keep the degree parities.

In order to bound the cost of the doubled spanning tree, we will need to use properties of the $T_F\triangle \{s,t\}$-join; more precisely, we will take a fractional solution in the $T_F\triangle \{s,t\}$-join polyhedron and write it as a convex combination of $T_F\triangle \{s,t\}$-joins, and then repeat the computation for each of the $T_F\triangle \{s,t\}$-joins in the convex combination.
In addition to computing several forest-based $\{s,t\}$-tours (with different $T_F\triangle\{s,t\}$-joins) for each $S\in \Sscr$, the algorithm also computes a Christofides-based $\{s,t\}$-tour, and  returns the least expensive among all constructed $\{s,t\}$-tours.
  (See Algorithm~\ref{alg:bomd} for a complete formalized description.)

\subsection{The Analysis and its Setting: Deletion, Correction, Completion, Reconnection, Balancing}\label{sub:co}


 
\begin{figure}
\begin{center}
$S_1$
\begin{tikzpicture}[->,shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,draw,font=\sffamily\bfseries\scriptsize}]

 
  \node[main node] (0) {$s$};
  
 \foreach \name/\pos in {{1/0}, {2/1}, {4/2}, {5/4}, {6/5}, {t/6}}
   \node[main node] (\name) [right of = \pos] {$\name$};

  \foreach \name/\pos in {{3/4}}
   \node[main node] (\name) [above of = \pos] {$\name$};
    
 \path[-,every node/.style={font=\sffamily}]
 	\foreach \source/\dest in {0/1,1/2,2/4,4/3,4/5,5/6,6/t}{
 		(\source) edge [very thick] node {} (\dest)	}
;
\end{tikzpicture}
\vspace{\baselineskip}

$S_2$
\begin{tikzpicture}[->,shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,draw,font=\sffamily\bfseries\scriptsize}]

 
  \node[main node] (0) {$s$};
  
 \foreach \name/\pos in {{1/0}, {2/1}, {4/2}, {5/4}, {6/5}, {t/6}}
   \node[main node] (\name) [right of = \pos] {$\name$};

  \foreach \name/\pos in {{3/4}}
   \node[main node] (\name) [above of = \pos] {$\name$};
    
 \path[-,every node/.style={font=\sffamily}]
	(t) edge [white, bend left] node {} (2)	
 	\foreach \source/\dest in {1/2,4/3,5/6,6/t}{
 		(\source) edge [very thick] node {} (\dest)	}
	\foreach \source/\dest in {0/3,5/2,3/6}{
		(\source) edge [thick, bend left] node {} (\dest)	} 			
	
;
\end{tikzpicture}
$S_3$
\begin{tikzpicture}[->,shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,draw,font=\sffamily\bfseries\scriptsize}]

 
  \node[main node] (0) {$s$};
  
 \foreach \name/\pos in {{1/0}, {2/1}, {4/2}, {5/4}, {6/5}, {t/6}}
   \node[main node] (\name) [right of = \pos] {$\name$};

  \foreach \name/\pos in {{3/4}}
   \node[main node] (\name) [above of = \pos] {$\name$};
    
 \path[-,every node/.style={font=\sffamily}]
 	\foreach \source/\dest in {0/1,1/2,4/3,4/5,5/6}{
 		(\source) edge [very thick] node {} (\dest)	}
	\foreach \source/\dest in {1/3,t/2}{
		(\source) edge [thick, bend left] node {} (\dest)	} 			
;
\end{tikzpicture}
\end{center}
\vspace{-\baselineskip}
\caption{$x^*$ from Figure~\ref{fig:Gao} expressed as a layered convex combination of three spanning trees $S_1,S_2,S_3$, each with multiplier $\lambda_{S_i}=1/3$. Note that $S_1$ is a so-called Gao-tree (see Section~\ref{sub:Gao}). All edges but $\{3,4\}$ are  lonely in $S_1$, and in $S_2$, $S_3$ only the edges incident to $s$ and $t$ are  lonely. }\label{fig:decomp}
\end{figure}

Given $x^*=\sum_{S\in \Sscr} \lambda_S S$, where $\Sscr$ is a set of spanning trees, $\lambda_S>0$ for $S\in \Sscr$, and $\sum_{S\in \Sscr} \lambda_S=1$, recall that this coefficient vector can be interpreted as a probability distribution. We will slightly abuse notation and let $\Sscr$ denote both the support of the convex combination, and  also  a tree-valued random variable with $\Pr(\Sscr=S)=\lambda_S$. (See Figure~\ref{fig:decomp} for such a convex combination, where $x^*$ is from Figure~\ref{fig:Gao}.)  

We will also take distributions over convex combinations of $T$-joins.  We let $\E{\cdot}$ denote the expectation or average of a random vector in $\mathbb{R}^E$;  for example $\E {\Sscr} = x^*$. 

For a spanning tree $S$, let $S(s,t)$ be the $s-t$ path of $S$.
Various notations for trees $S$ will be inherited by $\Sscr$ (and similarly for $T$-joins): for instance, $\Sscr(s,t)$ is the path-valued random variable which is equal to $S(s,t)$ on the event $\Sscr=S$. 



\subsubsection{Bounding the cost of the Christofides-based $\{s,t\}$-tours}
To analyze the average cost of the Christofides-based $\{s,t\}$-tours, we detail an observation of \cite{Sebo13}  used in the analysis of the best-of-many Christofides' algorithm.  
\begin{observation}\label{obs:offpath}
Since $S=S(s,t)+ S\setminus S(s,t)$, and for any $S\in \Sscr$, $S+ S \setminus S(s,t)$ is an $\{s,t\}$-tour,
defining
 $\displaystyle p^*:= \E{\Sscr(s,t)},\, q^*:= \E{\Sscr\setminus \Sscr(s,t)},\,  x^*=\E{\Sscr}= p^*+q^*\in \mathbb{R}^{E},$
the cost of the solution found by the best-of-many Christofides' algorithm can be bounded by
 \[\E{c(\Sscr)+ c(\Sscr\setminus \Sscr(s,t))}=c(x^*)+c(q^*)=2c(x^*)-c(p^*).\]
\end{observation}
When $c(q^*)$ is sufficiently small compared to $c(p^*)$, then this bound provides the best  approximation guarantee; when it is large, another bound is better, and it is shown  in~\cite{Sebo13} that the best of the two provides a bound of $8/5$ on the approximation and integrality ratio.  In Appendix~\ref{sec:8/5}, we rederive this bound in a surprisingly simple way.
\bigskip


In fact, since we will be taking the minimum of the Christofides-based $\{s,t\}$-tour and the forest-based $\{s,t\}$-tour, this observation allows us to ``erase'' $\Sscr\setminus \Sscr(s,t)$ from further consideration for parity correction, i.e., for analyzing the cost of the forest-based $\{s,t\}$-tours, we will only take the complementary $\Sscr(s,t)$ into account.

\subsubsection{Basic parity correction} 
Concretely, to analyze the parity correction for the forests, we will always use 
\begin{equation}\frac{x^*}{2}+\gamma\,{S(s,t)},\label{eq:BPC}\end{equation}
 as a so-called {\em basic parity correction}, where $\gamma$ is a chosen parameter between 0 and $1/2$. 
The basic parity correction plays a similar role to the vector $\beta \frac{x^*}{2}+ (1-\beta) S$ that was used in the analysis of  \cite{AnKS12}, which was also adopted by subsequent work \cite{Sebo13, Gao15, Vygen15,GottschalkV15}.

For $\gamma=1/2$  the basic parity correction $\frac{x^*}{2}+\frac12 {S(s,t)}$ for any $S\in \Sscr$ gives a feasible solution to the $T$-join polyhedron for any set $T$ of even size, so in particular it allows us to bound the cost of the $T_S\triangle \{s,t\}$-join. On average, the basic parity correction with $\gamma=1/2$ will equal $\frac{x^*}{2}+\frac{p^*}{2}$, and combined with Observation~\ref{obs:offpath}, we get the integrality gap and approximation ratio 
$\min\left\{\frac 32 c(x^*)+\frac12 c(p^*), 2c(x^*)-c(p^*)\right\}\le \frac53 c(x^*)$ equal to Hoogeveen's ratio. We can similarly use $\frac{x^*}{2}+\frac12 {S(s,t)}$ as a fractional $T_F\triangle \{s,t\}$-join for the forest $F=S\setminus L(S)$; however, the summand $\frac12{\Sscr(s,t)}$ is too expensive to get a good bound.

To improve the ratio further, we will need $\gamma<1/2$, but then the basic parity correction vector may not be feasible for the $T_F\triangle \{s,t\}$-join polyhedron. Hence, as  in previous analyses of the best-of-many algorithm, we will need to add a {\em parity completion}\footnote{Our terminology differs from that in~\cite{AnKS12}, where the term ``correction vector'' is used for what we call the ``parity completion vector''. We  use the term ``parity correction vector'' for a vector that is in the $T_F\triangle \{s,t\}$-join polyhedron, and it will be composed of basic parity correction and parity completions.}  vector to the basic parity correction vector so  as to  ensure the constraints of the $T_F\triangle \{s,t\}$-join polyhedron are satisfied for the narrow cuts $Q$ with $x^*(Q)<2-2\gamma$, in which $F$ contains an even number of edges.


However,  we cannot reduce $\gamma$ to 0, since the completion vectors are too expensive for large narrow cuts.  The treshold $2-\gamma$ for being ``large''  will be chosen optimally at the end of Section~\ref{sec:ratio}.  



\subsubsection{Parity completion}~\label{sub:completion}
The parity completion vector will add (fractional) edges for each narrow cut $Q$ if $|Q\cap F|$ is even. 
If we  define the set of lonely edges in tree $S$ by taking (\ref{eq:lonelysubset}) with equality, the expectation of the incidence vectors of the lonely edges for each narrow cut $Q$ is equal to a vector defined in Seb\H{o}~\cite{Sebo13}, which was used in~\cite{Sebo13} for defining good parity completion vectors. In particular, for each narrow cut $Q$, we introduce a vector $x^Q\in \mathbb{R}^E$, where 
\begin{equation}x^Q(e):=\Pr(e\mbox{ is the lonely edge of $\Sscr$ in $Q$}).\label{eq:xQ}\end{equation}
If  (\ref{eq:lonelysubset}) is satisfied with equality, then $\Pr(|Q\cap \Sscr|=1)=x^Q(Q)$ and 
\begin{equation}x^Q(Q)\ge 2 - x^*(Q),\label{eq:ineqxQbound}\end{equation}
 because 
$x^*(Q)=\E{|Q\cap \Sscr|} =\sum_{k=1}^\infty k \Pr(|Q\cap \Sscr|= k) \ge \Pr(|Q\cap \Sscr|=1) + 2 (1-\Pr(|Q\cap \Sscr| = 1))$. This is also observed in equation (3) of~\cite{AnKS12bis} as Markov's inequality.

As mentioned after  (\ref{eq:lonelysubset}),  $L(S)$ is allowed to be a proper subset of the right hand side of (\ref{eq:lonelysubset}), and the lonely edges will be chosen to satisfy additional properties.  One property  that we require now from the set of lonely edges $L(S)$ in addition to (\ref{eq:lonelysubset}), is that 
\begin{equation}x^Q(Q) = 2 - x^*(Q),\label{eq:xQbound}\end{equation}
 where we recall that $x^Q(Q)=\sum_{e\in Q}\Pr(L(\Sscr)\cap Q=\{e\})$. 
This equality can clearly be satisfied by removing edges from $L(S)$ for some $S\in \Sscr$ appropriately. 

Hence, we have that
$\frac{x^*(Q)+x^Q(Q)}{2}= 1,$
on every cut.
In other words, adding $x^Q/2$ to the basic parity correction vector for every $Q$ such that $|Q\cap F|$ is even gives a suitable vector to {\em complete} parity correction, that is, for {\em parity completion}. 

On the other hand, if we let $\Fscr$ be the random forest obtained by deleting $L(\Sscr)$ from $\Sscr$, then we also have that $x^Q(e)$ is the {\em deletion probability} for edge $e$ and cut $Q$. So by deleting the lonely edges from $\Sscr$, we ``save up'' for parity completion.
In Section~\ref{sec:ratio}, we show how to put these ingredients together to construct an appropriate parity correction vector $y_F$, and we analyze its mean cost over $S\in \Sscr$.



\subsubsection{Reconnection}\label{subsub:reconnection}
Finally,  we need to bound the average cost of the {\em doubled minimum cost spanning tree $2D_{F+J_F}$  between the components of $(V, F+J_F)$},  meaning the doubled edge-set of a spanning tree in the graph whose vertex-set is the set of contracted components of $(V, F+J_F)$. 
Note that doubling a minimum cost spanning tree  between the components of $(V, F+J_F)$ gives the minimum possible cost of the reconnection of $F+J_F$ if using  {\em only}  doubled edges; for bounding the expectation of  $2D_{\Fscr+J_\Fscr}$  we can therefore  consider  any set of doubled edges that reconnect the forest.

For a tree $S\in \Sscr$, denote by $\Qscr(S)\subseteq \Qscr$ the set of {\em lonely cuts} of $S$: cuts $Q$ for which $|Q\cap S|=1$ for which the unique edge in $Q\cap S$ is in $L(S)$. For $Q\in \Qscr(S)$, we denote by $e_S^Q$ the (incidence vector of) the unique edge of  $Q\cap S$.

Since  $F=S\setminus L(S)$, $J_F$ must contain at least one edge in every cut in $Q\in \Qscr(S)$, since $|F\cap Q|$ is even (and equal to 0). Now, if each edge in $J_F$ is contained in at most one lonely cut, then $(V, F+J_F)$ is connected, and the  doubled spanning tree is empty, its cost is $0$. We will call the edges that are contained in more than one lonely cut of $S$ the {\em bad edges} for $S$, and denote them by $B(S)$, that is,
\[B(S) = \{e\in E:  \hbox{there exist $Q_1\ne Q_2\in \Qscr(S)$},\, e\in Q_1\cap Q_2\}.\]
Ideally, we would like a low cost $T_F\triangle \{s,t\}$-join $J_F$ (or, a fractional $T_F\triangle \{s,t\}$-join $y_F$) that has no edges in $B(S)$. Figure~\ref{fig:doubling} shows a forest $F$ and a $T_F\triangle \{s,t\}$-join $J_F$ with two bad edges.

As we sketched above, our fractional $T_F\triangle \{s,t\}$-join is going to consist of the basic parity correction $\frac{x^*}{2}+\gamma S(s,t)$ plus a parity completion vector for which we will use the $x^Q$ vectors for $Q\in \Qscr$. There is no way to avoid that the basic parity correction vector contains bad edges, but we will choose our convex combination of $x^*$ into spanning trees in such a way that parity completion does not add more bad edges (see sections~\ref{sub:Gao} and~\ref{sec:decomp} for more details). 

Given the parity correction vector $y_F$ that we construct, we consider a random $T_F\triangle \{s,t\}$-join $\Jscr_F$ with $\E{\Jscr_F}=y_F$.
In Section~\ref{sec:doubling} we give an upper bound on the expected cost of the doubled spanning tree $2D_{F+\Jscr_F}$, where the expectation is over $\Jscr_F$.
For any $e\in E$, we define $\Qscr(S,e)$ as the set of lonely cuts of $S$ that contain $e$; note that  $b\in B(S)$ if and only if  $|\Qscr(S,b)|\ge 2$.
We can upper bound the cost of $2D_{F+\Jscr_F}$ by, for each bad edge $b\in \Jscr_F$, taking two copies of each lonely edge in $S\cap\Qscr(S,b)$ except possibly one such lonely edge; so the cost can be  upper bounded by doubling the cost of
\begin{equation}
\bigcup_{b\in \Jscr_F}\{ e_S^Q: \mbox{ for all but at most one $Q$ in }\Qscr(S,b)\}.\label{DF}
\end{equation}
\begin{figure}
\begin{center}
\begin{tikzpicture}[->,shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,draw,font=\sffamily\bfseries\scriptsize}]

 
  \node[main node] (0) {$s$};
  
 \foreach \name/\pos in {{1/0}, {2/1}, {4/2}, {5/4}, {6/5}, {t/6}}
   \node[main node] (\name) [right of = \pos] {$\name$};

  \foreach \name/\pos in {{3/4}}
   \node[main node] (\name) [above of = \pos] {$\name$};

   
  \path[-,every node/.style={font=\sffamily}]

	(3) edge [very thick] node {} (4)
 	\foreach \source/\dest in {0/3,3/4,3/6,6/t}{
 		(\source) edge [red, very thick, bend left] node {} (\dest)	}
 	\foreach \source/\dest in {0/1,1/2,2/4,4/5,5/6,6/t}{
 		(\source) edge [dashed] node {} (\dest)	}

;
\end{tikzpicture}
\end{center}
\vspace{-\baselineskip}
\caption{The forest $F_1:=F(S_1)$ obtained by removing the lonely edges from $S_1$ in Figure~\ref{fig:decomp} contains only the edge $\{3,4\}$ indicated in (solid) black, the dashed edges are the lonely edges  of  $S_1$. The (solid) red edges give a possible $T_{F_1}\triangle \{s,t\}$-join $J_{F_1}$, where edges $\{s,3\}$ and $\{3,6\}$ are bad edges.
An upper bound on $2D_{F_1+J_{F_1}}$  can be obtained by adding two copies of  two out of the three lonely edges $\{s,1\}, \{1,2\}, \{2,4\}$ and adding two copies of either $\{4,5\}$ or $\{5,6\}$.
}\label{fig:doubling}
\end{figure}

The challenge that is addressed in Section~\ref{sec:doubling} is to decide for which $Q\in \Qscr(S,b)$ we do {\em not} add two copies of the edge $e_S^Q$. The goal is to choose it so that on average (over all $J_F\in \Jscr_F$), we get a good bound on the number of times we use $e_S^Q$, and hence on the cost of $2D_{F+\Jscr_F}$. Note that $\E{e_S^Q}=x^Q$, and we thus express the cost of reconnection in terms of the vectors $\{x^Q\}_{Q\in \Qscr}$ as well. 

\subsubsection{Balancing}
To bound the average cost of the forest-based $\{s,t\}$-tours, we now simply add up the average cost of the forest plus parity correction (consisting of basic parity correction and parity completion) plus reconnection. 
By noting that $\sum_{Q\in \Qscr} x^Q \le \E{\Sscr(s,t)}=p^*$ (since the lonely edges of spanning trees $S$ must be contained in $S(s,t)$),  all terms of the bound on the average cost of the forest-based $\{s,t\}$-tours will be expressable in terms of $x^*$ and $p^*$.
Finally, the  analyis can take  the minimum of the  Christofides-based $\{s,t\}$-tours (which by Observation~\ref{obs:offpath} has cost decreasing in $c(p^*)$) and the cost of the forest-based $\{s,t\}$-tours is increasing in $c(p^*$). The worst case for the minimum of the two is when the two are {\em balanced}, that is equal. 


\subsection{Matroid Partition to Avoid Additional Reconnection}\label{sub:Gao}

Besides the improved algorithm, and the main ideas of the analysis, there is an important, technical looking detail that has to be handled: as explained in the previous subsection, not only parity, but connectivity  also has to be corrected  if the $T_F\triangle \{s,t\}$-join contains bad edges. 
We show in Section~\ref{sec:decomp} that when choosing a convex combination of trees in a particular way that can be computed with Edmonds' ``matroid partition algorithm'', parity completion does not  contribute to the probability of bad edges occurring in the $T_F\triangle \{s,t\}$-join.  Let us introduce the reader to this nontrivial matter.

In a beautiful paper \cite{Gao13},  Gao showed that there always exists a spanning tree $S$ in the support of $x^*$ (that is, in $S\subseteq \{e:x^*(e)>0\}$) such that $|S\cap Q|=1$ for every narrow cut $Q$. Whenever there exists such a  minimum cost spanning tree that satisfies this property  (like for ``graph-metrics'') the $3/2$ ratio and integrality gap follow straightforwardly. 
 A tree in which every narrow cut is {\em lonely}, that is, contains a single edge of the tree,  is called a {\em Gao-tree}.

The interesting idea of {\em choosing the convex combination of spanning trees in a particular way}, so as to decrease the cost of parity completion, was introduced in Vygen~\cite{Vygen15}. The claimed progress in the ratio was only $0.001$, but the idea of reassambling the trees $S\in \Sscr$ which participate in the convex combination is further developed by Gottschalk and Vygen~\cite{GottschalkV15}.  They  generalize the concept of Gao-trees, and the reassambling leads to a powerful result: a convex combination using  generalized Gao-trees. Although the use of local changes is constructive, the algorithm it implies is not a polynomial time algorithm. However,  using an approximate solution to this convex combination that can be found in polynomial time,  Gottschalk and Vygen state that the best-of-many algorithm gives a $1.566$-approximation and integrality ratio for the $s-t$ path TSP.


\medskip
In Section~\ref{sec:decomp}  we prove that (generalized) Gao-trees form a matroid, and that a  convex combination into these trees can be found as a corollary of Edmonds' matroid partition algorithm \cite{Edm70}  (see also \cite[Theorem 13.3.1]{Fra11}, \cite[Corollary 42.1a]{Schrijver-book}).  As a consequence, a ``suitable'' convex combination  is constructed directly (without a posteriori reassambling or exchanges), 
in strongly polynomial time,  from the matroid partition algorithm applied to the matroids of  (generalized) Gao-trees.

We note that, independent of our work, Kanstantsin Pashkovich also pointed out that this convex combination can be found (in weakly polynomial time) using the ellipsoid method [Jens Vygen, private communication, 2016]. 

We will use the term ``layered'' to refer to the resulting convex combination:
 We say that  the spanning tree $S$ of $G$ with lonely edges $L(S)$ and consequently defined lonely cuts $\Qscr(S)$
 is {\em layered}, if
 \[\mbox{for each $Q\in\Qscr(S)$ and cut $Q'$ such that  $x^*(Q')\le x^*(Q)$ we have $Q'\in \Qscr (S)$,}\]
that is, $Q'$ is also lonely in $S$ if it is smaller than another cut $Q$  lonely in $S$.
We say that the tree-valued random variable  $\Sscr$,  or the convex combination of spanning trees  $\Sscr$ with coefficients $\lambda_S$ for $S\in\Sscr$ is {\em layered},  if $\E{\Sscr}=x^*$, (\ref{eq:lonelysubset}), (\ref{eq:xQbound}) hold, and each $S\in \Sscr$ is layered.  


In  Section~\ref{sec:decomp} the existence and (strongly) polynomial algorithm for finding a layered convex combination will be confirmed.  We can view these results as strengthenings of (\ref{eq:xQbound}), which states that the larger the cut, the more rarely it is lonely; in a layered convex combination this is true in the stronger sense of the containment (implication) of events. In order to achieve this, we exploit the possibility of proper containment in (\ref{eq:lonelysubset}), i.e., $\Qscr(S)$ may be a proper subset of $\{Q\in \Qscr: |Q\cap S|=1\}$. 


We finish this section by showing  how layered convex combinations allow us to avoid additional reconnection costs.  We also state the theorem that converts this to a simple bound on the total of reconnection costs; the proof is deferred to Section~\ref{sec:doubling}.
\begin{lemma}\label{lem:goodpcl} 
	Let $\Sscr$ be layered, $S\in\Sscr$, and  $Q\in\Qscr\setminus\Qscr(S)$.  
	Then $x^Q(B(S))=0$.  
\end{lemma}
\prove We prove  $x^Q(Q')=0$ for each $Q'\in\Qscr(S)$. Indeed, since $S$ is layered, $x^*(Q') < x^*(Q)$, for otherwise $Q\in\Qscr(S)$.  But then using that $\Sscr$ is layered, $Q'$ is lonely in every tree $S'\in\Sscr$ where $Q$ is lonely, so $Q$ and $Q'$ cannot have a common edge in such a tree $S'$, proving $x^Q(Q')=0$. 

Therefore, the edges $e$ with $x^Q(e)>0$ are not contained in any $Q\in\Qscr(S)$ at all, whereas the edges of $B(S)$ are contained in at least two cuts of $\Qscr(S)$. \qed

\medskip Algorithm~\ref{alg:bomd} loops through a layered $\Sscr$, and has an inner loop through the support $\Jscr_F$ of a convex combination of $T_F\triangle\{s,t\}$-joins, for each $F\in\Fscr:=\Sscr\setminus L(\Sscr)$.  Consider the corresponding  $T_F\triangle\{s,t\}$-join valued random variable $\Jscr_F$ (with $\E{\Jscr_F}=y_F$) that {\em accompanies} $F$. (In Algorithm~\ref{alg:bomd}, the inner loop determines a minimum cost reconnecting edge-set $2D_{F+J_F}$ for every $J_F$ in the support of $\Jscr_F$,  thus derandomizing the random $T_F\triangle\{s,t\}$-join $\Jscr_F$ that accompanies $F$.)

\begin{theorem}\label{thm:summary}  Assume  $\Sscr$ is layered, $S\in \Sscr$, and 
$F=S\setminus L(S)$ is accompanied by  $\Jscr_F$. Then
	\[\E{c(2D_{F+\Jscr_F})} \le  \sum_{Q_\in\Qscr(S)}(x^*(Q)-1)c(e_S^Q).\]
\end{theorem}



\section{The New Ratio}\label{sec:ratio}


In this section we prove the main result, relying on Theorem~\ref{thm:summary}.  
It may be useful for the reader to consult Appendix~\ref{sec:3/2} at this point, where we show how the bound $3/2$ can be proved more simply for special cases, without the need for Theorem~\ref{thm:summary}.  

\begin{theorem}\label{thm:main}
The Best-of-Many With Deletion (BOMD) algorithm returns a solution to the $s-t$ path TSP of cost at most $\left(\frac32+\frac1{34}\right)\lin$.
\end{theorem}

\medskip
\prove
We analyze the different parts of the forest-based $\{s,t\}$-tour $P_1(S)$ averaged over $S\in \Sscr$.
\begin{itemize}
\item[]
	{\bf Forest}:  Let $\Fscr:=\Sscr\setminus L(\Sscr)$.
	
	{\em Expected Value of Forest :} $\E{\Fscr}=\displaystyle x^* - \sum_{Q\in\Qscr}x^Q$.
	
\item[]	
{\bf Parity Correction} (PC): For each forest $F$, we define $y_F$ as the sum of the following vectors:
	
\begin{enumerate}
	\item[]	{\bf Basic Parity Correction} (BP):
	$\frac{1}{2}x^* + \gamma\, S(s,t)$.  
	
	Note that (BP) is enough to ensure that $y_F$ satisfies the constraints of the $T_F\triangle \{s,t\}$-join polyhedron for all $Q=\delta(U)$ with $x^*(Q)\ge 2-2\gamma$.
	
	{\em Expected Value of (BP):} $\displaystyle \frac{1}{2}x^* + \gamma\, p^*.$
	
	\item[]	{\bf Parity Completion for Empty Cuts } (PCE): $\displaystyle \left(1-\frac12 x^*(Q)-\gamma\right) e_S^Q.$
	
	We recall that $e_S^Q$ is the (indicator vector of) the lonely edge of $S$ in $Q$. We add this (PCE) vector to $y_F$ for every $Q\in \Qscr(S)$ such that $x^*(Q)\le 2-2\gamma$.
	Note that then (BP)+(PCE) suffices to ensure that $y_F$ satisfies the constraint  of the $T_F\triangle \{s,t\}$-join polyhedron for each narrow cut $Q$  such that $Q\cap F=\emptyset$.
	Since $\E{e_{\Sscr}^Q}=x^Q$, we have:
	
	{\em Expected Value of (PCE):} $\displaystyle\sum_{Q\in \Qscr:\,x^*(Q)\le 2-2\gamma}\left(1 -  \frac12x^*(Q) - \gamma\right)x^Q.$
	
	\item[]	{\bf Parity Completion for Non-Empty Even Cuts} (PCL): $\displaystyle\left(\frac{1 - \frac12 x^*(Q)-\gamma}{2 - x^*(Q)}\right)\,x^Q.$
	
	We add this vector to $y_F$ for every $Q$ such that $x^*(Q)\le 2-2\gamma$ and $|F\cap Q|$ is even and at least 2.  	
	By~(\ref{eq:xQbound}), $y_F$ satisfies the constraints of the $T_F\triangle \{s,t\}$-join polyhedron also for narrow cuts such that $|F\cap Q|$ is even and non-zero.\\
	Contrary to (PCE), (PCL) does not depend on (the outcome of the random variable) $\Sscr$, but only on the cut $Q\in\Qscr$. However, the choice of adding it or not, depends on $\Sscr$: we add it only if $|\Fscr\cap Q|$ is even and at least two, the probability of which can be bounded by $\Pr(|\Sscr\cap Q|\ge 2)$, which is at most $1-\left(2-x^*(Q)\right)$ by (\ref{eq:xQbound}), so we add (PCL) with probability at most $x^*(Q)-1$:
	
	{\em Expected Value of (PCL):}$\displaystyle \sum_{Q\in \Qscr:\,x^*(Q)\le 2-2\gamma}(x^*(Q)-1)\left(\frac{1 -  \frac12x^*(Q) -\gamma}{2 -  x^*(Q)}\right)x^Q.$
\end{enumerate}


The combination of the parts (BP) + (PCE) + (PCL) gives a fractional solution to the $T_F\triangle \{s,t\}$-join polyhedron for any fixed tree $S$ and its uniquely determined forest $F=S\setminus L(S)$ :
\begin{eqnarray}
y_F &=& \frac12x^*+\gamma\, S(s,t) + \sum_{Q\in \Qscr:x^*(Q)<2-2\gamma,  |Q\cap F|=0} \left(1-\frac12x^*(Q)-\gamma\right) e_S^Q \nonumber\\
&&+ \sum_{Q\in \Qscr:x^*(Q)<2-2\gamma, |Q\cap F|\ge 2, \mathrm{even}} \left(\frac{1 - \frac12 x^*(Q)-\gamma}{2 - x^*(Q)}\right)\,x^Q.\label{yF}\end{eqnarray}	



\item[]	{\bf Reconnection}:  For each $S\in\Sscr$, define the random $T_F\triangle \{s,t\}$-join  $\Jscr_F$  with $\E{\Jscr_F}=y_F$. By Theorem~\ref{thm:summary}:  	
	{\em Expected Value of Reconnection Cost:}  $\E{c(2D_{\Fscr+\Jscr_\Fscr})} \le \sum_{Q\in \Qscr}(x^*(Q) - 1)c(x^Q)$. 
\end{itemize}
	\bigskip\noindent
	{\bf TOTAL}: 
If we add up the costs of the bounds on the different parts of the solution, we get $\frac32 c(x^*)+\gamma c(p^*)$ plus the sum over all $Q\in \Qscr$ of some multiple (that depends on $x^*(Q)$) of $c(x^Q)$. In particular, if $2-2\gamma<x^*(Q)< 2$, the multiplier of $c(x^Q)$ is $-1+x^*(Q)-1=x^*(Q)-2\le 0$, and if $x^*(Q)\le 2-2\gamma$  it is
\[-1 + \left(1 -  \frac12x^*(Q) -\gamma\right) \left(1 + \frac{x^*(Q)-1}{2 -  x^*(Q)}\right)+x^*(Q)-1= \frac{2 -  x^*(Q) -2\gamma}{2(2-x^*(Q))}+ x^*(Q)-2.\]
We choose $\gamma$ so that this multiplier is nonpositive for all $Q\in \Qscr$, that is, we want
\[2 -  x^*(Q) -2\gamma + 2(2-x^*(Q))(x^*(Q)-2)\le 0 \hbox{  that is,  } (2-x^*(Q)-\frac{1}{4})^2 +\gamma -\frac{1}{16} \ge 0.\]
The minimum of $\gamma$ for which this is satisfied for all $1\le x^*(Q)\le 2$ is $\gamma=\frac{1}{16}$, where we note that equality holds if and only if $x^*(Q)=\frac74$.

We have thus bounded the average cost of the $P_1(\Sscr)$ solutions by $\frac32 c(x^*) + \frac1{16}c(p^*)$.
By Observation~\ref{obs:offpath}, the average cost of the $P_2(\Sscr)$ solutions is at most $2c(x^*)-c(p^*)$, and therefore  the cost of the solution returned by (BOMD)  is at most  
\[\min\left\{\frac32 c(x^*) + \frac1{16}c(p^*), 2c(x^*)-c(p^*)\right\} = \left(\frac32+\frac1{34}\right)c(x^*).\]\qed



\section{Bounding the Reconnection Cost}\label{sec:doubling}
In this section we provide a  bound, tight in some sense, on the cost of the doubled spanning tree $c(2D_{F+J_F})$ between the components of $(V, F+J_F)$, as explained in Section~\ref{subsub:reconnection}.  

We fix $S$ and $F=S\setminus L(S)$, and in this section, we think of $\Jscr_F$ as representing a random $T_F\triangle\{s,t\}$-join, with $\E{\Jscr_F}=y_F$. Recall that (\ref{DF}) gives us a way to upper bound the expected cost of  $2D_{F+\Jscr_F}$: for each bad edge  $b\in\Jscr_F$, we add two copies of the lonely edges $e_S^Q$ for {\em all but at most one of the lonely cuts $Q\in \Qscr(S,b)$ that contain $b$}. We will say that the edges for which two copies are added are {\em used for reconnection}.  Obviously, the best bound is obtained by choosing to omit the most expensive lonely edge; however, for our analysis, we will randomly choose the cut $Q\in \Qscr(S,b)$ for which we {\em do not} add two copies of the edge $e_S^Q$ for reconnection. Note  that we are free to determine the probability distribution and, for simplicity, we also allow not choosing any of the cuts. 
We denote
\[x(b,Q) := \Pr(e_S^Q \hbox{ is not used for reconnection }| \hbox{ $b\in \Jscr_F$}),\]
and describe a system of linear inequalities that turns out to express that  $\{x(b,Q):b\in B(S), Q\in\Qscr (S) \}$ is a suitable set of conditional probabilities (  as will be shown in  Lemma~\ref{lem:probound}):

\[x(b,Q)\ge 0 ,\quad \hbox{ for all } b\in B(S),  Q\in\Qscr (S,b), \leqno{(D0)}\]
\[\sum_{Q\in \Qscr(S,b)}x (b, Q) \le 1 \hbox{ for all $b\in B(S)$, }\leqno{(D1)}\]
\[\sum_{b\in B(S)\cap Q}x^*(b)x (b, Q)
\ge r_Q, \hbox{for all $Q\in \Qscr(S)$, }\leqno{(D2)} \]
where  $r_Q:= 1 - x^*(Q\setminus B(S))$. 

\medskip
Note that $r_Q$ can be negative, in which case the constraint is vacuously satisfied.




 
The conclusion of the following lemma, Lemma~\ref{lem:probound}, will lead to Theorem~\ref{thm:summary}; the conditions of Lemma~\ref{lem:probound} will be assured by two additional lemmas: Lemma~\ref{lem:feasibility} and Lemma~\ref{lem:goodpcl}. 

\begin{lemma}\label{lem:probound} Let $Q\in\Qscr(S)$, and suppose $\Pr(b\in \Jscr_F)\le x^*(b)/2$ for each $b\in B(S)$.
	Let $x(b,Q):=\Pr(e_S^Q \hbox{ is not used for reconnection }| b\in \Jscr_F)$,  then
	\[\Pr(e_S^Q \hbox{ is used for reconnection })\le \frac{x^*(Q)-1}{2},\]
	provided $\{x(b,Q):Q\in \Qscr(S),b\in B(S)\}$ satisfy ($D2$).
\end{lemma}

\prove  
By the law of total probability:
\[\Pr(e_S^Q \hbox{ is used for reconnection })= \sum_{b\in B(S)}(1-x (b, Q))\,\Pr(b\in \Jscr_F),  \]
 where we can substitute the condition $\Pr(b\in \Jscr_F)\le x^*(b)/2$, and arrive at
\[\Pr(e_S^Q \hbox{ is used for reconnection })\le\sum_{b\in B(S)}\frac{x^*(b)}{2}\,(1-x (b, Q)),\,
\hbox{ for all $Q\in \Qscr(S)$. } \]

Therefore, the claimed inequality holds provided that
\[\sum_{b\in B(S)}(x^*(b)/2)(1-x (b, Q))
\le \frac{x^*(Q)-1}{2}, \hbox{ for all $Q\in \Qscr(S)$. } \]

Multiplying by $2$ and rearranging, we get that this inequality is equivalent to
\[-\sum_{b\in B(S)}x^*(b)x (b, Q)
\le x^*(Q)-1 - \sum_{b\in B(S)}x^*(b), \hbox{ for all $Q\in \Qscr(S)$, }\]
which is exactly ($D2$) multiplied by $-1$.
\qed

\medskip
Despite the seemingly rough bounding, all of the applied inequalities in the series are best possible in the following sense:  the resulting inequality cannot be improved with our methods, not even if there is only one narrow-cut-size in addition to $1$ (which is a special case of Appendix~\ref{subsub:one}).

\begin{lemma}\label{lem:feasibility}
	The system of linear inequalities (D0), (D1), (D2) is feasible for all $S\in\Sscr$.
\end{lemma}

\medskip
\prove Let $S\in\Sscr$. Farkas' lemma provides a necessary and sufficient condition for feasibility.
The special structure of the bipartite matching constraints ($D1$), ($D2$) makes possible to simplify this condition to the following K\H{o}nig-Hall type characterization (in fact equivalent to the K\H{o}nig-Hall theorem for $f$-factors or transportation problems:  

\begin{claim}\label{claim:KH}The system of linear inequalities ($D0$), ($D1$), ($D2$) is feasible if and only if for all $\Qscr'\subseteq \Qscr(S)$:
	\[ \sum_{Q\in \Qscr'} r_Q\le x^*(\cup_{Q\in\Qscr'} Q\cap B(S) ) \]
\end{claim}


The proof that this condition is indeed necessary and sufficient can be done for instance by a reduction to a transportation problem.
Let $K$ be the least common denominator of $x^*$. We create a transportation problem with $|\Qscr(S)|$ demand nodes, one for each $Q\in \Qscr(S)$, with demand $r_Q$, and $K|B(S)|$ supply nodes, each with supply 1. Note that there are thus $K$ supply nodes $b^1,\ldots, b^K$ corresponding to bad edge $b$; for each $Q\in \Qscr(S)$ such that $b\in Q$, we create $K$ arcs $(b^i,Q)$ for $i=1,\ldots, K$. One can show that if there exists a solution to this transportation problem then there exists a solution in which for each $b,Q$, the flow on the arcs $(b^i, Q)$ is equal for $i=1,\ldots, K$ . Such a solution is exactly a solution to ($D0$), ($D1$), ($D2$). 

For self-containedness and since a formal reduction would take at least as much space, we provide a direct proof in terms of inequalities in  Appendix~\ref{app:KH}. 

\medskip
Therefore, what we have to prove is that the condition of Claim~\ref{claim:KH} is satisfied by $x^*$.
Let $\Qscr'\subseteq\Qscr(S)$. Then
\[\sum_{Q\in\Qscr'}r_Q=\sum_{Q\in\Qscr'} (1-x^*(Q\setminus B(S)))=|\Qscr'| -\sum_{Q\in\Qscr'}x^*(Q\setminus B(S)).\]
According to Claim~\ref{claim:KH}, what we have to show is that this quantity is at most $x^*(\cup_{Q\in\Qscr'} Q\cap B(S))$, which is exactly the content of Claim~\ref{claim:cuts}:
 
\begin{claim}\label{claim:cuts}
	$x^*(\cup_{Q\in\Qscr'} Q)\ge  |\Qscr'|.$
\end{claim}
Indeed, denote $k:=|\Qscr'|$, and let $C_0, \ldots, C_{k}$ the vertex sets of  components of $S\setminus \cup_{Q\in\Qscr'}e_S^Q,$ where $s\in C_0, t\in C_k$. Since $\{C_0,\ldots,C_k\}$ is a partition of $V$, every edge is counted twice in the sum of their coboundaries:
\[x^*(\cup_{Q\in\Qscr'}Q)=\frac{1}{2}\sum_{j=0}^k x^*(\delta(C_i))\ge \frac 12 (x^*(\delta(C_0))+\sum_{j=1}^{k-1} x^*(\delta(C_j)) + x^*(\delta(C_k)))\ge \frac 12 (1+ 2(k-1)+1)=k,\]
exactly as claimed, finishing the proof of Claim~2 and of Lemma~\ref{lem:feasibility}.  
\qed



\subsection*{Proof of Theorem~\ref{thm:summary} and Restated Algorithm}\label{sub:inner}

We are now ready to prove  Theorem~\ref{thm:summary} putting together  Lemmas~\ref{lem:probound}, \ref{lem:feasibility} and ~\ref{lem:goodpcl}. As a bonus, the proof reveals that the inner loop of our algorithm can be replaced by an appropiate definition of the objective function for the $T_F\triangle \{s,t\}$-join that anticipates the reconnection cost. We finish this section by developing this.




\medskip
\noindent {\bf Proof of Theorem~\ref{thm:summary}}: Let $\Jscr_F$ be a random $T_F\triangle \{s,t\}$-join with $\E{\Jscr_F}=y_F$ (see Section~\ref{sec:ratio}) that is ``derandomized'' by the algorithm. We prove: 
\[\E{c(2D_{F+\Jscr_F})} \le  \sum_{Q_\in\Qscr(S)}(x^*(Q)-1)c(e_S^Q)\]
On the event $\Jscr_F = J_F$ the least possible cost for  reconnecting $F+J_F$ with pairs of doubled edges is $c(2D_{F+J_F})$. 
Another possible way of reconnecting is to add for all $b\in J_F\cap B(S)$, the lonely edges of $\Qscr(S,b)$ doubled, except one of them, as explained in  (\ref{DF}) and the lines above it. Hence, we have
\begin{equation}
c(2D_{F+J_F}) \le \sum_{b\in J_F\cap B(S)}\left(-\max_{Q\in \Qscr(S,b)}2c(e_S^Q) + \sum_{Q\in \Qscr(S,b)}2c(e_S^Q)\right).\label{eq:cost}
\end{equation}	
Now we prove that the right hand side of this equation can be upper-bounded by the right hand side of the assertion of the theorem, by randomizing the choice of the unique cut in $\Qscr(S,b)$ for which the lonely edge is not used for reconnection, and then applying Lemma~\ref{lem:probound}:

Note that the basic parity correction part of $y_F(b)$ is equal to $x^*(b)/2$ for $b\in B(S)$, and we thus
need to show that the (PCE) and (PCL) vectors occurring for tree $S$ are 0 for edges in $B(S)$.

This is immediately true for (PCE): $e_S^Q$ for $Q\in\Qscr(S)$ is by definition contained in exactly one cut of $\Qscr(S)$, while the edges in $B(S)$ are those contained in at least two such cuts.
The fact that this also holds for (PCL) is exactly the conclusion of  Lemma~\ref{lem:goodpcl}. 
  Hence, the condition of Lemma~\ref{lem:probound} that $Pr(b\in \Jscr_F)\le x^*(b)/2$ for every $b\in B(S)$ is satisfied.

Lemma~\ref{lem:feasibility} makes sure that one can define a probability distribution so that the (conditional) probabilities give a valid choice (by ($D0$) and ($D1$)) and satisfy ($D2$).  So Lemma~\ref{lem:probound} can indeed be applied, that is,
$\Pr(e_S^Q \hbox{ is used for reconnection })\le \frac{x^*(Q)-1}{2}$ for every $Q\in \Qscr(S)$. When $e_S^Q$ is used for reconnection, it is doubled, so its contribution to the costs is $2c(e_S^Q)$, and therefore the expectation of the described random reconnection cost is  $\sum_{Q\in \Qscr(S)}(x^*(Q)-1)c(e_S^Q)$.
\qed
\medskip

We now show  how the counting of the above proof can be used to remove the inner loop (over all $J_F\in \Jscr_F$)  from our algorithm.
Since the expected reconnection cost $2D_{F+J_F}$ can be upper bounded using (\ref{eq:cost}) and it is in fact this value that is upper bounded in Theorem~\ref{thm:summary}, we can replace $2D_{F+J_F}$ in the algorithm and in the summary of the analysis in Theorem~\ref{thm:main} as well: rather than letting $2D_{F+J_F}$ be  a doubled minimum cost spanning tree, we let it denote the edge set of which the cost is given by the right hand side of~(\ref{eq:cost}).


Redefining the objective function for the computation of a minimum  cost $T_F\triangle \{s,t\}$-join in the following way can then replace the inner loop (over the $T_F$-joins of $\Jscr_F$): for any $e\in E\setminus B(S)$ let 
$c'(e)=c(e)$, and for $b\in B(S)$ let
\[c'(b) := c(b)-\max_{Q\in \Qscr(S,b)}2c(e_S^Q) + \sum_{Q\in \Qscr(S,b)}2c(e_S^Q).\]
Then  the minimum $c'$-cost $T_F\triangle \{s,t\}$-join $J^*_F$ anticipates the cost of the reconnection with $2D_{F+J_F}$ as well. Since our analysis bounded the $c'$-cost of a convex combination of $T_F\triangle \{s,t\}$-joins this bound also applies to $c'(J^*_F)$.

We summarize  the revised algorithm using the specifications of this section in Algorithm~\ref{alg:bomd2}.
\begin{algorithm}[!h]
	\caption{Restated Best-of-Many With Deletion }\label{alg:bomd2}
	{
		Let $x^*$ be an optimal solution to the subtour elimination LP for the $s-t$ path TSP.\;
		Write $x^*$ as a layered convex combination of spanning trees. \;
		Let $\Sscr$ be the collection of trees with positive coefficient.\;
		\For{$S\in \Sscr$}
		{
			{\bf Construct forest-based $\{s,t\}$-tour:}\;
			$F:=F(S):=S\setminus L(S)$.\;
			Let $c'(e)=c(e)$ for all $e\in E\setminus B(S)$.\;
			Let $c'(b)=c(b) + \sum_{Q\in \Qscr(S,b)}2c(e_S^Q)-\max_{Q\in \Qscr(S,b)}2c(e_S^Q).$ for all $b\in B(S)$.\;
			Let $J^*_F$ be a minimum cost $T_F\triangle \{s,t\}$-join with respect to costs $c'$.\;
			Contract the components of $(V, F+J^*_F)$, and let $2D_{F+J^*_F}$ be the edge set of a doubled minimum cost spanning tree on the contracted graph.\;
			$P_{1}(S)=F+J^*_F+2D_{F+J^*_F}$.\;
			{\bf Construct Christofides-based $\{s,t\}$-tour:}\;
			$P_{2}(S)=S+J_S$, where $J_S$ is a minimum cost $T_S\triangle \{s,t\}$-join with respect to costs $c$.\;
		}
		Return a minimum cost $\{s,t\}$-tour from among  $\bigcup_{S\in \Sscr}\{P_1(S), P_2(S)\}$. 
	}
\end{algorithm}



\section{Layered Trees through Matroid Partition}\label{sec:decomp}

In this section we prove that a layered $\Sscr$, $\E{\Sscr}=x^*$ exists, and can be found in a combinatorial way and strongly polynomial time.
Recall that this means for $Q\in\Qscr(S)$ $(S\in \Sscr)$ and $x^*(Q)\ge x^*(Q')$, that $Q'$ is also lonely.

Note that an arbitrary convex combination is not necessarily layered  (see Figure~\ref{fig:nonmonotone}).


\begin{figure}
\begin{center}
$S_1$
\begin{tikzpicture}[->,shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,draw,font=\sffamily\bfseries\scriptsize}]

 
  \node[main node] (0) {$s$};
  
 \foreach \name/\pos in {{1/0}, {2/1}, {4/2}, {5/4}, {6/5}, {t/6}}
   \node[main node] (\name) [right of = \pos] {$\name$};

  \foreach \name/\pos in {{3/4}}
   \node[main node] (\name) [above of = \pos] {$\name$};
    
 \path[-,every node/.style={font=\sffamily}]
 	\foreach \source/\dest in {0/1,1/2,4/3,4/5,5/6,6/t}{
 		(\source) edge [very thick] node {} (\dest)	}
 		(5) edge [thick, bend left] node {} (2)		
;
\end{tikzpicture}
\vspace{\baselineskip}

$S_2$
\begin{tikzpicture}[->,shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,draw,font=\sffamily\bfseries\scriptsize}]

 
  \node[main node] (0) {$s$};
  
 \foreach \name/\pos in {{1/0}, {2/1}, {4/2}, {5/4}, {6/5}, {t/6}}
   \node[main node] (\name) [right of = \pos] {$\name$};

  \foreach \name/\pos in {{3/4}}
   \node[main node] (\name) [above of = \pos] {$\name$};
    
 \path[-,every node/.style={font=\sffamily}]
 	\foreach \source/\dest in {1/2,2/4,4/3,4/5,5/6,6/t}{
 		(\source) edge [very thick] node {} (\dest)	}
 		(0) edge [thick, bend left] node {} (3)		
;
\end{tikzpicture}
\vspace{\baselineskip}

$S_3$
\begin{tikzpicture}[->,shorten >=1pt,auto,node distance=1cm,
  thick,main node/.style={circle,draw,font=\sffamily\bfseries\scriptsize}]

 
  \node[main node] (0) {$s$};
  
 \foreach \name/\pos in {{1/0}, {2/1}, {4/2}, {5/4}, {6/5}, {t/6}}
   \node[main node] (\name) [right of = \pos] {$\name$};

  \foreach \name/\pos in {{3/4}}
   \node[main node] (\name) [above of = \pos] {$\name$};
    
 \path[-,every node/.style={font=\sffamily}]
 	\foreach \source/\dest in {0/1,1/2,4/3,5/6}{
 		(\source) edge [very thick] node {} (\dest)	}
	\foreach \source/\dest in {1/3,t/2,3/6}{
		(\source) edge [thick, bend left] node {} (\dest)	} 			
;
\end{tikzpicture}
\end{center}
\caption{$x^*$ from Figure~\ref{fig:Gao} expressed as a convex combination of three spanning trees $S_1,S_2,S_3$, each with multiplier $\lambda_{S_i}=1/3$, that is {\em not} layered. Note that $x^*(Q_j)=5/3$ for $j=2,\ldots, 5$, that there is exactly one $S_i$ for which $|Q_j\cap S_i|=1$, so in order for (\ref{eq:xQbound}) to hold, $Q_j$ has to be lonely in the unique tree $S_i$ such that $|Q_j\cap S_i|=1$. But then, for example, $Q_2$ is lonely in $S_1$, but $Q_3$ is not.}\label{fig:nonmonotone}
\end{figure}




\bigskip
Let the different cut-sizes of narrow cuts be $2-\zeta_1>2-\zeta_1-\zeta_2>\ldots >2-\zeta_1-\ldots-\zeta_k= 1$,
\[\hbox{and  }\Qscr_i:=\{Q\in\Qscr: x^*(Q)\le 2-\zeta_1-\ldots-\zeta_i\},\]
\[\Bscr_i:=\{ S\subseteq E :\hbox{$S$ is a spanning tree of $G$, $|S\cap Q|=1$ for all $Q\in\Qscr_i$ }\},\]
that is, $\Bscr_i$ is the set of spanning trees of $G=(V,E)$ for which every cut $Q\in\Qscr_i$  contains exactly one edge. Clearly, $\sum_{i=1}^k \zeta_i=1$, and  $\Bscr_1\subseteq \ldots \subseteq \Bscr_k$.


The following is a fractional (so weaker) version of Edmonds'  matroid  partition theorem in the form that we need it (see close versions  to which it can be reduced \cite[Chapter 42]{Schrijver-book}):

\begin{theorem}\label{thm:matroidpartition}
	Let $M_i=(E,r_i)$ $(i=1,\ldots,k)$ be matroids, $w\in\mathbb{R}^E$, and $\lambda_i\in \mathbb{R}$, $0\le \lambda_i\le 1$ $(i=1,\ldots,k)$.
	Let $P^i$ be the convex hull of independent sets of $M_i$.
	There exist $x^i\in P^i$ for $i=1,\ldots, k$ such that:
	\begin{equation}
	\sum_{i=1}^k\lambda_ix^i=w,\, \label{concl:matroidpartition}
	\end{equation}
\begin{equation}
\hbox{if and only if for all $X\subseteq E:$} \sum_{i=1}^k\lambda_i r_i(X) \ge w(X).
\label{cond:matroidpartition}
\end{equation}
	
\end{theorem}



\medskip
We say that edge $e\in E$ is in {\em layer} $i$ $(i\in\{1,\ldots,k\}$), if there is a unique cut $Q\in\Qscr_i$ such that $e\in Q$.  Edges may also be in several or no layers. Since $\Qscr_1\supseteq \ldots \supseteq \Qscr_k$, the layers in which an edge is contained are consecutive numbers. (If it is contained exactly in layers $i\in [a,b]\cap\mathbb{N}$, then it is contained in at least $2$ cuts of  $\Qscr_i$ for $i<a$, and in none of the cuts $\Qscr_i$ for $i>b$.) 
Denote $L_i:=\{e\in E: \hbox{$e$ is in layer $i$}\}$. So we can think of layer $i$ to be the set $\L_i$ of ``Gao edges'' for the cuts $\Qscr_i$. The edges Gao used for his solution \cite{Gao13} were those of $L_1$. 

Following and generalizing Gao \cite{Gao13} we call sets of the form $W\setminus U\ne\emptyset$ where $s\in U\subseteq W$,  $Q=\delta(U)\in\Qscr$, $R=\delta(W)\in\Qscr$, {\em level-sets.} If in addition, $Q,R\in\Qscr_i$, $W\setminus U$ will be called a {\em level-set of layer $i$}. Gao \cite[Lemma~3.2]{Gao13} proved that  {\em level-sets induce connected subgraphs of} $G$.  The natural ordering  of chains induces a natural ordering of (inclusionwise) minimal level-sets starting with $\{s\}$ and ending with $\{t\}$. What Gao calls level sets are the  minimal level sets of layer $1$. In the Appendix we extend his connectivity result by proving that level-sets of $\Qscr_i$ are  in fact $\zeta_1+\ldots + \zeta_i$-connected (Lemma~\ref{lem:disGao}), and show the connection with layered convex combinations of spanning trees. We  use here only that 
\begin{equation}
L_i\cap Q\ne\emptyset\, \hbox{ for all $Q\in\Qscr_i$ $(i=1,\ldots,k$)}\hbox{ and the level-sets induce connected graphs.}\label{eq:nonempty}
\end{equation}
that can be  checked anew, or as a special case of \cite[Lemma~3.2]{Gao13}, or apply Lemma~\ref{lem:disGao} in Appendix~\ref{sec:matroids}.

Denote $G_i:=E\setminus \bigcup_{Q\in \Qscr_i}Q$. Let $M_i:=(E,r_i)$ $(i=1,\ldots, k)$ be the matroid whose independent sets are of the form $F_i\cup C_i$, where $F_i$ is a forest in $G_i$ and $C_i\subseteq L_i$, $|C_i\cap Q|\le 1$ for each $Q\in\Qscr^i$. (Such sets form the independent sets of a matroid, as straightforward from the fact that the forests of any graph form the independent sets of a matroid.) The set of bases of $M_i$ will be denoted by $\Bscr_i$. Clearly, $B\in\Bscr_i$ if and only if $B$ meets each component of $G_i$ in a spanning tree, and meets each cut of $\Qscr_i$ in exactly $1$ edge. According to (\ref{eq:nonempty}), $\Bscr_i\ne\emptyset$. Summarizing: 
\begin{equation}
M_i:=(E,r_i) \hbox{ is a matroid, and its rank is $r_i(E)=n-1$ $(i=1,\ldots, k)$.}\label{eq:matroid}
\end{equation}



We first establish the connection between layered convex combinations and these matroids:


\begin{lemma}\label{lem:equivalent}
	The following statements are equivalent:
	\begin{itemize}
		\item []{\rm (i)} There exists a layered convex combination. 
			\item []{\rm (ii)} There exists a convex combination  
			$\sum_{S\in \Sscr} \lambda_S S=x^*$
			$(\lambda_S>0$ for $S\in \Sscr$, $\sum_{S\in \Sscr} \lambda_S=1)$ of spanning trees, and $k$  nonnegative integers $1\le m_1\le \ldots \le m_k=|\Sscr|,$ so that the trees in the first $m_i$ terms of the sum are in $\Bscr_i$, and the sum of the first $m_i$ coefficients is  $\sum_{j=1}^i\zeta_j$  (for all $i=1,\ldots,k)$. 
		\item []{\rm (iii)} The equation  (\ref{concl:matroidpartition}) holds, where $w=x^*$ and $P^i$ is the convex hull of $\Bscr_i$,  $\lambda_i=\zeta_i$ $(i=1,\ldots,k)$. 
	\end{itemize}
	Furthermore, finding (i), (ii) or (iii) are (strongly) polynomially equivalent. 
\end{lemma} 

\prove If (ii) holds, the sum of the coefficients from the first term and the  $m_1$-th term is $\zeta_1$, and the trees are in $\Bscr_1$. From the $m_i+1$-th until the $m_{i+1}$-th term the sum of the coefficients is $\sum_{j=1}^{i+1}\zeta_j - \sum_{j=1}^i\zeta_j=\zeta_{i+1}$,  and the trees are in $\Bscr_{i+1}$ $(i=1,\ldots, k-1)$, by the constraint of (ii). This is exactly a combination of spanning trees in the form of (\ref{concl:matroidpartition}), with the specifications of (iii). So (iii) is proved. 

Consider now a convex combination in the form of  (\ref{concl:matroidpartition}) with the specifications of (iii). 
Substitute for $x^i$  a convex combination of $\Bscr_i$, and let  $x^*=\sum_{i=1}^k \sum_{S\in \Bscr_i} \lambda_{S} S$ be the corresponding convex combination of $x^*$ into spanning trees, where $\zeta_ix^i=\sum_{S\in \Bscr_i} \lambda_S S$. 
\begin{equation}\mbox{The set of lonely edges $L(S)$ for $S\in \Bscr_i$ is defined as $S\cap L_i$.}\label{eq:lonelydef}\end{equation}
By the definition of $L_i$ (\ref{eq:lonelysubset}) is satisfied, moreover by (\ref{eq:nonempty}) then $\Qscr(S)=\Qscr_i$. In order to prove (i), it remains to check that $S$ is layered, and according to  the definition end of Section~\ref{sub:Gao} this means that $Q\in\Qscr_i$ and $x^*(Q')\le x^*(Q)$ for a cut imply $Q'\in\Qscr_i$, which is obviously true. 

Finally, suppose that (i) holds, and let 	$\sum_{S\in \Sscr} \lambda_S S=x^*$ be a layered convex combination. In this sum, order the trees $S$ in decreasing order of the  largest cut-size among the cuts in $\Qscr (S)$. Then group the ties, that is, form $k$ groups of sums (some of which may be empty) of trees whose lonely cuts have the same maximum cut size $2-\zeta_1,\ldots,2-\zeta_1-\ldots - \zeta_i, \ldots , 2-\zeta_1,\ldots,2-\zeta_1-\ldots - \zeta_k$ respectively. Since $\Sscr$ is layered, for the trees $S$ in the $i$-th group $\Qscr_i\subseteq \Qscr (S)$, and therefore in the first $i$ groups there are only trees in $\Bscr_i$.  


Let $m_i$ be the number of trees in the first $i$ groups $(i=1,\ldots,k)$. By (\ref{eq:xQbound}) which is satisfied by $L(S)$ (see the lines after (\ref{eq:xQbound}) or the definition of layered at the end of Section~\ref{sub:Gao}) the probability that a cut of size $2-\zeta_1-\ldots - \zeta_i$ contains a lonely edge is exactly $\zeta_1+\ldots + \zeta_i$,  and this happens exactly for the trees of the first $i$ groups, so $m_i=\sum_{j=1}^i \zeta_i$,  which provides a convex combination of the form of (ii).
\qed

 By Theorem~\ref{thm:matroidpartition} and Lemma~\ref{lem:equivalent}, a layered convex combination exists if and only if (\ref{cond:matroidpartition}) holds for our matroids, and then it can be determined in polynomial time:

\begin{theorem}\label{thm:layered}
	The matroids $M_i$ $(i=1,\ldots k)$ satisfy (\ref{cond:matroidpartition}) with $w=x^*$, $\lambda_i=\zeta_i$, and $r_i$ the rank function of the matroid $(E,\Bscr_i)$; a layered convex combination exists and can be determined in strongly polynomial time, by running the matroid partition algorithm once.
\end{theorem}


\prove
The existence of a  convex combination satisfying  Lemma~\ref{lem:equivalent} (ii) has already been proved using an interesting, but technically demanding local  procedure, ``tree-reassambling'', by Gottschalk and Vygen \cite{GottschalkV15}, without the matroid property. So by Lemma~\ref{lem:equivalent} we have (iii) as well, and therefore, by the easy part of the matroid partition theorem, Theorem~\ref*{thm:matroidpartition} this implies (\ref{cond:matroidpartition}). Running Edmonds' matroid partition algorithm (see the references below) it cannot terminate with a violated condition, so it will terminate by finding a convex combination that satisfies (ii), which, again by Lemma~\ref{lem:equivalent} implies (i), that is, a layered convex combination, as claimed.
\qed


\medskip


Note that our proof uses the result of \cite{GottschalkV15} to check that (\ref{cond:matroidpartition}) holds; however, checking that (\ref{cond:matroidpartition})  holds for a particular set of matroids is usually a straightforward task, that would provide a direct simpler proof for the existence of layered decompositions as well. Lemma~\ref{lem:disGao}  (Appendix~\ref{sec:matroids}) shows a direct algorithmic  proof for the existence of  a  basis-packing in  $M_i$ for all $i\in\{1,\ldots,k\}$ respecting  the capacity function $x^*$ with sum of coefficients $\zeta_1+\ldots + \zeta_i$. This is  weaker than a layered convex combination: it is explained in Appendix~\ref{sec:matroids} that having only one packing satisfying each of these $k$ properties simultaneously would be sufficient  for (and is equivalent to) a layered convex combination, that is, to (\ref{cond:matroidpartition}) or (\ref{cond:basispacking}). However, when this manuscript is submitted, we have not completed a direct approach for  proving this.

\medskip
For actually finding a layered convex combination through tree packing, the proofs are algorithmic provided a testing membership problem in tree polyhedra is available. (\cite[Chapter 51, mainly 51.4]{Schrijver-book}; or it may be better to use general matroid bases packing, see also Edmonds' ``matroid base packing theorem''\cite{Edm65} (a straightforward consequence of Edmonds' matroid partition theorem) \cite[13.3.13]{Fra11}, \cite[Corollary 42.1d]{Schrijver-book}, and execute any weighted algorithm giving priority to smaller index matroids; for the polynomial solvability of matroid basis packing we refer to \cite{Cunningham84}, and at \cite[page 891]{Schrijver-book}  the exact competitive complexities can be checked.) The rank oracle can be computed in linear time for all our matroids $M_i=(E,r_i)$ as well: 
$r_i(X)=|V| - c(X\setminus \bigcup_{Q\in \Qscr_i}Q)+ |Q\in\Qscr_i: Q\cap L_i\ne\emptyset|$, where $c(Y)$ $(Y\subseteq E)$  denotes the number of connected components of $(V, Y)$.


\bigskip
We conclude by summarizing the overall proof of our bounds from a bird's eye view: Theorem~\ref{thm:layered} allows us to avoid additional reconnection costs, by ensuring that the parity completion part of the parity correction vector does not contribute to the probability of requiring reconnection across a lonely cut (Lemma~\ref*{lem:goodpcl}). This is an important ingredient in  the proof of Theorem~\ref*{thm:summary}, which bounds the total expected reconnection cost. Another important component of the bound of Theorem~\ref*{thm:summary} is provided by Section~\ref{sec:doubling}, where we define a probability distribution that determines which lonely edges to use for reconnection, thus allowing us to ``allocate'' the cost of reconnection to the lonely cuts.  Then Theorem~\ref*{thm:summary} itself is used in the improved ratio that is our main result, Theorem~\ref{thm:main}.


\begin{thebibliography}{99}
	\addtolength{\itemsep}{-3pt}
	
\bibitem{AnKS12}
H.~Ch.~An, R.~D.~Kleinberg, and D.~B.~Shmoys.
\newblock Improving Christofides' algorithm for the s-t path {TSP}.
\newblock In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC'12).
\newblock Revised in \cite{AnKS12bis}.	
	
\bibitem{AnKS12bis}
H.~Ch.~An, R.~D.~Kleinberg, and D.~B.~Shmoys.
\newblock Improving Christofides' algorithm for the s-t path {TSP}.
\newblock {\em J. {ACM}}, 62(5):34, 2015.

\bibitem{Barahona95}
F.~Barahona.
\newblock Packing spanning trees.
\newblock {\em Mathematics of Operations Research}, 20(1):104--115, 1995.


\bibitem{CheriyanFG15}
J.~Cheriyan, Z.~Friggstad, and Z.~Gao.
\newblock Approximating minimum-cost connected t-joins.
\newblock {\em Algorithmica}, 72(1):126--147, 2015.

\bibitem{Christofides76}
N.~Christofides.
\newblock Worst case analysis of a new heuristic for the traveling salesman
problem.
\newblock Report 388, Graduate School of Industrial Administration,
Carnegie-Mellon University, Pittsburgh, PA, 1976.

\bibitem{Cook11}
W.~J.~Cook.
\newblock {\em In Pursuit of the Traveling Salesman: Mathematics at the Limits
	of Computation}.
\newblock Princeton University Press, December 2011.

\bibitem{Cunningham84}
W.~Cunningham.
\newblock Testing membership in matroid polyhedra,
\newblock {\em Journal of Combinatorial Theory, Series B}, 36:161--188, 1984.


\bibitem{DantzigFJ54}
G.~Dantzig, R.~Fulkerson, and S.~Johnson.
\newblock Solution of a large-scale traveling-salesman problem.
\newblock {\em Operations Research}, 2:393--410, 1954.


\bibitem{Edm65}
J.~Edmonds.
Lehman's switching game and a theorem of Tutte and Nash-Williams,
{\em J. of Research of the National Bureau of Standards,}
Section B 69 (1965),
pp.\ 125--130.

\bibitem{Edm70}
J.~Edmonds.
Submodular functions, matroids and certain polyhedra.
{\em In: Combinatorial Structures and Their Applications},
Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications 1969
(R.~Guy, H.~Hanani, N.~Sauer, J.~Sch\"onheim, eds.),
Gordon and Breach, New York 1970, pp.\ 69--87.


\bibitem{EdmJ73}
J.~Edmonds, and  E.~L.~Johnson.
Matching, Euler tours and the Chinese postman.
{\em Mathematical Programming}, 5 (1973), 88--124.

\bibitem{Fra11}
A. Frank.
Connections in Combinatorial Optimization.
Oxford University Press 2011.

\bibitem{Gao13}
Z.~Gao.
\newblock An {LP}-based 3{/}2-approximation algorithm for the {\it s}-{\it t}
path graph {T}raveling {S}alesman {P}roblem.
\newblock {\em Oper. Res. Lett.}, 41(6):615--617, 2013.

\bibitem{Gao15}
Z. Gao.
\newblock On the metric s-t path traveling salesman problem.
\newblock {\em {SIAM} J. Discrete Math.}, 29(3):1133--1149, 2015.

\bibitem{GarJT76}
M.~R.~Garey, D.~S.~Johnson, and R.~E.Tarjan.
\newblock The planar hamiltonian circuit problem is np-complete.
\newblock {\em SIAM Journal on Computing}, 5(4):704--714, 1976.

\bibitem{GottschalkV15}
C.~Gottschalk and J.~Vygen.
\newblock Better {\it s}-{\it t} -tours
by Gao trees.
\newblock {\em CoRR}, abs/1511.05514, 2015.

\bibitem{Hoogeveen91}
J.~A.~Hoogeveen.
\newblock Analysis of Christofides' heuristic: Some paths are more difficult
than cycles.
\newblock {\em Operations Research Letters}, 10(5):291 -- 295, 1991.

% \bibitem{JohnsonP85}
% D.~S.~Johnson and C.~H.~Papadimitriou.
% \newblock Performance guarantees for heuristics, in:
% \newblock {\em The Traveling Salesman Problem -- A Guided Tour of Combinatorial Optimization} (E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, eds.) Wiley, Chichester, 1985, pp. 145 -- 180.


\bibitem{NW61}
C.St.J.A.~Nash-Williams.
\newblock Edge-disjoint spanning trees of finite graphs,
\newblock {\em The Journal of the London Mathematical Society}, 36, 445--450, 1961.

\bibitem{Schrijver-book}
A.~Schrijver.
\newblock {\em Combinatorial Optimization - Polyhedra and Efficiency}.
\newblock Springer, 2003.

\bibitem{Sebo13}
A.~Seb\H{o}.
\newblock Eight-fifth approximation for the path {TSP}.
\newblock In {\em Proceedings of the 16th International Conference on Integer
	Programming and Combinatorial Optimization (IPCO)}, pages 362--374, 2013.

\bibitem{SV}
A.~Seb\H{o}, J.~Vygen, Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs,  {\em Combinatorica}, {\bf 34} (5) October (2014), 597--629.

	
	\bibitem{Sebo14}
	A.~Seb{\H{o}}.
	\newblock Problems about uniform covers, with tours and detours.
	\newblock In {\em Matematisches Forschungsinstitut Oberwolfach Report No.~51/2014, DOI: 10.4171/OWR/2014/51, November 2014}, on joint work with Y.~Benchetrit and M.~Stehl\'\i k,  pages 2912--2915, March 2015.
	
	\bibitem{Tutte61}
	W.T.~Tutte.
	\newblock On the problem of decomposing a graph into $n$ connected factors,
	\newblock {\em The Journal of the London Mathematical Society}, 36, 221-230, 1961.

\bibitem{Vygen15}
J.~Vygen.
\newblock Reassembling trees for the traveling salesman.
\newblock {\em CoRR}, abs/1502.03715, 2015.

\bibitem{Wolsey80}
L.~A.~Wolsey.
\newblock Heuristic analysis, linear programming and branch and bound.
\newblock {\em Mathematical Programming Study}, 13:121--134, 1980.
	
\end{thebibliography}


\newpage
\centerline{\large\bf  APPENDIX}

\bigskip
The appendix contains further illustrations of our techniques and additional results.  In Appendix~\ref{sec:8/5}, we  illustrate  our setting and analysis on the best-of-many Christofides' algorithm (without deletion) with a very short  proof of the guarantee of 8/5.
In Appendix~\ref{sec:3/2}, we show that the deletion of lonely edges gives tight results in certain cases. In each of these part of the difficulties disappear, which allows to focus better on those that remain. In 
Appendix~\ref{app:KH}, we give a self-contained proof of Claim~\ref{claim:KH}, and in Appendix~\ref{sec:matroids} we provide a new matroid construction inspired by Section~\ref{sec:decomp}. We also show a partial direct proof for the layered convex combination and exhibit what is missing from a full matroidal proof.  



\appendix

\section{Our Setting and Analysis for BOMC}\label{sec:8/5}

Let us say that a narrow cut $Q$ is small if $1\le x^*(Q)\le \frac32$, and large, if $\frac32\le x^*(Q)<2$. (If $x^*(Q)=\frac32$ it is both small and large.) 
We begin by considering the cases when all narrow cuts are small  or  all  are large.  

Throughout Appendix~\ref{sec:8/5},  we take $L(S)$ to be the set of edges of $S$ that are the unique edge in some narrow cut, i.e., (\ref{eq:lonelysubset}) will hold with equality, and we can apply (\ref{eq:ineqxQbound}).
 
 \subsection{All Narrow Cuts Are Small}\label{subsec:allsmall} 
 If all narrow cuts are small, then the probability that $|Q\cap \Sscr|$ is even is at most $x^*(Q)-1\le \frac12$ by (\ref{eq:ineqxQbound}). Also, by (\ref{eq:ineqxQbound}), the vector $\tfrac{x^*}{2} + \sum_{Q\in \Qscr: |Q\cap S|\mathrm{\ even}}\tfrac{x^Q}{2}$ is in the $T_S\triangle \{s,t\}$-join polyhedron.
 Hence, the average or expected parity correction can be bounded by $\tfrac12 x^*+\sum_{Q\in \Qscr}\tfrac 12 \tfrac{x^Q}{2}\le \tfrac12 {x^*}+\tfrac14 p^*$, where the inequality follows by noting that if $e$ is the lonely edge in narrow cut $Q$ in some tree $S$, then $e$ must be on the $s-t$ path in $S$, so $\sum_{Q\in {\cal Q}} x^Q \le \E{\Sscr(s,t)}=p^*$.
 So, if all narrow cuts are small, we can again bound the cost of the best-of-many solution by $\tfrac32 c(x^*)+\tfrac14c(p^*)$, and combined with Observation~\ref{obs:offpath}, this implies a bound of $\tfrac85c(x^*)$ for this case as well.

\subsection{All Narrow Cuts Are Large}
If all narrow cuts are large, then the basic parity correction vector  (\ref{eq:BPC}) with $\gamma=\tfrac14$ yields already as good a vector as the best one in the ``All Small'' case: it is in the  $T_S\triangle \{s,t\}$-join polyhedron for {\it any} $S$, since by assumption $x^*(Q)\ge \tfrac32$ for all $Q$.

Hence, the average cost of the spanning tree plus parity correction is at most $c(x^*)+\tfrac12c(x^*)+\tfrac14c(p^*)$.
Using Observation~\ref{obs:offpath}, we can also bound the cost by $2c(x^*)-c(p^*)$, and since $\min\{\tfrac32 c(x^*)+\tfrac14 c(p^*), 2c(x^*)-c(p^*)\} \le \tfrac85 c(x^*)$, we get the desired result.



\subsection{Combining the Two Cases}\label{subsub:eightfifth}
It turns out that  the two extreme cases described above can be ``merged'' by essentially taking the average of the two, and surprisingly without having any extra cost. We  show two, slightly different proofs of the ratio $8/5$ of \cite{Sebo13}: the first, applying systematically the setting of the present paper, the second, even simpler, pointing more at the intuitive ``averaging merge" also constituting a bridge to the original solution, that we include as a remark.  

\begin{itemize}
	\item[] {\bf Connectivity:} Tree $\Sscr$.
	
	{\em Expected Value of Connectivity}: $\E{S}=x^*$.
	
	\item[] {\bf Parity Correction:} The cost of a $T_S\triangle \{s,t\}$-join can be upper bounded by the cost of a point in the $T_S\triangle \{s,t\}$-join polyhedron, which is the sum of the following two vectors:
	\begin{enumerate}
		\item[] {\bf Basic Parity Correction} (BP): $\frac12x^*+\gamma\, S(s,t)$.	
		{\em Expected Value of (BP)}: $\frac12x^*+\gamma\, p^*$.
		\item[] {\bf Parity Completion for Even Cuts} (PCL): 
		$\displaystyle \left(\frac{2 - 2\gamma- x^*(Q)}{2-x^*(Q)}\right) \frac{x^Q}{2}$.

		We add a parity completion term for narrow cut $Q$ and tree $S\in \Sscr$  only if $|Q\cap S|$ is even, and  $x^*(Q)\in [1,2(1-\gamma))$.
		By (\ref{eq:ineqxQbound}), (BP)+(PCL) is a vector in the $T_{S}\triangle \{s,t\}$-join polyhedron for each $S\in\Sscr$. 	
		Since we add (PCL) for $Q$ with probability $1-x^Q(Q)\le x^*(Q)-1$ by (\ref{eq:ineqxQbound}), the expectation of the (PCL) vector is at most 
		$\displaystyle \sum_{Q\in \Qscr:x^*(Q)<2(1-\gamma)}\frac{\left(1-\gamma-x^*(Q)/2\right)\left(x^*(Q)-1\right)}{2-x^*(Q)} x^Q$.
		
		For each $Q\in\Qscr$ the coefficient of $x^Q$ in this sum is at most
			\[\left(1-\gamma-\frac x2\right)\frac{x-1}{2-x},\]
		where $x=x^*(Q)$. 
		For fixed $\gamma$, the unique maximum of this expression in the interval $[1,2]$ is $x=2-\sqrt{2\gamma}$. Substituting this in the formula we find that the unique minimum is $\gamma=\frac18$, when the worst cut-size is $x=2-\sqrt{2\times\frac18}=\frac32$, the unique intersection of  small and large cut-sizes.  Substituting these values into our bound, we get that the coefficient of $x^Q$ for all $Q\in\Qscr$ is at most $\frac18$. 

		Finally note that if $e$ is the lonely edge in narrow cut $Q$ in some tree $S$, then $e$ must be on the $s-t$ path in $S$, so (PCL) is finally bounded by $\frac18\sum_{Q\in {\cal Q}} x^Q \le \frac18\E{\Sscr(s,t)}=\frac18 p^*$.
	
	{\em Expected Value of (PCL):}  $\le \frac18 p^*$.
	\end{enumerate}

	{\em Expected Value of Parity Correction:}  $\frac12x^*+ \frac14 p^*$.	
\end{itemize}
The total expected cost of the solution can thus again be bounded by $\tfrac32 c(x^*) + \tfrac 14 c(p^*)$. 
Combined with Observation~\ref{obs:offpath}, we can bound the cost of the constructed solution by $\tfrac85 c(x^*)$.

\medskip\noindent{\bf Remark:}
We can also arrive at this solution without optimizing over $\gamma$, with less computation: 

 
For the bounds in the  ``all small'' and ``all large'' case the unique  worst cut-size is $x=\frac 32$.  Take a  convex combination (for instance with $\frac12$ coefficients, leading to their arithmetic mean), of the two parity correction vectors $\pi_1$ and $\pi_2$ that  ``even cuts'' receive in the two cases respectively:  $\pi_1:=\tfrac12x^*+\sum \tfrac{x^Q}{2}$ and $\pi_2:= \tfrac12x^*+\tfrac14 p^*$. Then 
$\pi:=\frac{\pi_1+\pi_2}{2}=\tfrac12x^*+\tfrac 12 \sum \tfrac{x^Q}{2} + \tfrac18 p^*$  is certainly a valid parity completion vector  for even cuts of size $\frac32$, as it is the convex combination of two valid parity correction vectors. 

In fact, since $\pi$ contains the term $\tfrac18 p^*$, the vector is automatically valid for even cuts of size at least $\tfrac74$. Moreover, if we replace $\pi$ by $\tfrac12 x^*+ \sum\left(\frac{7/4-x^*(Q)}{2-x^*(Q)}\right) \frac{x^Q}{2}+\tfrac18 p^*$ (where we have to add the middle term only for even cuts), then we get a valid parity correction vector. By (\ref{eq:ineqxQbound}), we add the middle term with probability $x^*(Q)-1$ for each $Q\in \Qscr$, so the mean value of parity correction is at most  
 \[\tfrac12 x^*+ \sum_{Q\in\Qscr}(x^*(Q) -1) \left(\tfrac{7/4-x^*(Q)}{2-x^*(Q)}\right) \tfrac{x^Q}{2}+\tfrac18 p^*\]
 Now, for $1\le x<2$, 
	\[\left(\frac78-\frac x2\right)\frac{x-1}{2-x} \le \frac 18.\]
(Multiply both sides of the inequality by $2-x>0$, $(\tfrac78-\tfrac x2)(x-1) - \tfrac18(2-x)=-\tfrac {x^2}2+\tfrac{3x}2-\tfrac98 = -\tfrac18(2x-3)^2\le 0$.) So we got the same bound  as in the two special cases.

\section{Tight Bound on the Integrality Gap for Special Cases}\label{sec:3/2}

We show some simple cases where the ratio and integrality gap $3/2$ can be proved. 
\subsection {Disjoint and Almost-Disjoint Narrow Cuts}\label{subsec:disjoint}
 Let  $G=(V,E)$ be a graph and denote $\mathbf{1}$ be the all-$1$ vector on  the edges. A naturally arising open question relaxing the integrality gap of the subtour elimination LP is to determine the smallest constant $\alpha$ so that $\alpha \mathbf{1}$ is {\em feasible}, that is,  a convex combination of $T$-tours\footnote{A $T$-tour is a connected graph in which the set of odd degree vertices is $T$.}~\cite{Sebo14}:
 
For $3$-edge-connected graphs $\mathbf{1}$ is always feasible. Indeed, setting $2/3$ on all the edges is in the (dominant of the) convex hull of spanning trees and $1/3$ is in the (dominant of the) convex hull of $T$-joins for every $T$. It has been pointed out that this result is not best possible. Indeed,  the conjecture that the integrality gap of the subtour elimination LP is $\tfrac43$ for the metric TSP is well-known to be equivalent to the feasibility of $\frac43 x$ provided $x$ is in the subtour polytope. Therefore, if this conjecture is true, $\alpha=\frac43\cdot\frac23=\frac89$ is also feasible for $T=\emptyset$, 
which may be a weaker and more hopeful conjecture to prove than the $\frac43$-conjecture about the integrality gap.

However, if $T\ne\emptyset$ the integrality gap is at least $3/2$ (see~\cite{AnKS12bis} for an example for $T=\{s,t\}$), and it follows that $\alpha\ge 1$ is necessary for  $\alpha \mathbf{1}$ to be feasible. Instead of $3$-edge-connectivity we have to require then only that $T$-even cuts  (that is, cuts $\delta(U)$, $U\subseteq V$, $|T\cap U|$ is even) are of size at least $3$. The conjecture that the integrality gap of the subtour elimination LP is $\tfrac32$ implies that $\alpha=\frac32\cdot \frac23=1$ already defines a feasible vector, that is, $\mathbf{1}$ is feasible for such graphs. 

Our techniques allow us to prove shortly that this is indeed true, that is:

\noindent
{\em If all $T$-even cuts of $G$ are of size at least $3$, $\mathbf{1}$ is a convex combination of $T$-tours.} For $T$-tours, narrow cuts are also defined, and have similarly nice properties. They do not form a chain, but they do form a laminar system~\cite{CheriyanFG15}. 
 Since we will see that we do not need reconnection here, our proof can be extended to this case, but for ease of communication we restrict ourselves to $T=\{s,t\}$ in the following. Then the condition means just that identifying $s$ and $t$ we get a  $3$-edge-connected graph. The generalization for arbitrary $T$ is straightforward. 


\begin{theorem}
Let $G=(V, E)$ be a connected graph, $s,t\in V$ and let $|\delta(U)|\ge 3$ for any $|U\cap \{s,t\}|\neq 1$.
Then, $\mathbf{1}$ can be expressed as a convex combination of $\{s,t\}$-tours.
\end{theorem}
\prove We can suppose that $G$ is $2$-edge-connected, since a cut-edge necessarily separates $s$ and $t$, and we can proceed by induction, separating the problem into two.  
Note also  that $x^*(e)=\tfrac23$ on every $e\in E$ is a feasible solution to the subtour elimination LP for $s-t$ path TSP. Hence, we can use the BOMD algorithm on $x^*$, where the narrow cuts are exactly the $s-t$ cuts of $G$ containing two edges. We will show that the forest-based $\{s,t\}$-tours $F+J_F$ give us the desired convex combination; in other words, that reconnection is never needed.


 \begin{itemize}
 	\item[] {\bf Forest:} We take an arbitrary decomposition of $x^*$ into spanning trees $S\in \Sscr$, and let $F:=F(S):= S\setminus L(S)$.\\
 	 	{\em Expected Value of Forest:} $x^* -\sum_{Q\in\Qscr}x^Q$.
 	\item[] {\bf Parity Correction} (PC): We take $y_F$ to be the basic parity correction vector with $\gamma=0$, and we add as parity completion $x^Q/2$ for every narrow cut $Q$ such that $|Q\cap F|$ is even. As observed in Section~\ref{sub:completion}, this indeed gives a feasible parity correction vector.\\
 	{\em Expected Value of (PC):} $\frac12x^*+\frac12\sum_{Q\in \Qscr} x^Q$.
 	\item[] {\bf Reconnection:} Note that the fact that the non-$s-t$-cuts of $G$ have at least three edges implies that {\em the narrow cuts are pairwise disjoint}:
 	

 	Indeed, suppose there exist narrow cuts $Q_1=\delta(U_1), Q_2=\delta(U_2)$ (each containing exactly two edges), $s\in U_1$, $t\in U_2$ and $Q_1\cap Q_2\ne\emptyset$ Then the left hand side of (\ref{eq:submodularity}) is $2\cdot\frac23+2\cdot\frac23$, and the first term of the right hand side is $3\cdot\frac23=2$ by the condition of the theorem; the last term on the right hand side is at least $2\cdot \frac23$ because a common edge, that exists by the non-emptiness asumption, has one endpoint in $U_1\setminus U_2$ and the other in $U_2\setminus U_1$. Since $\frac43\ne \frac53$ this is a contradiction. 
\medskip

 	 	It follows that there are no bad edges, since these are contained in at least two narrow cuts:
 	
 	\noindent
 	{\em Expected Value of Reconnection:} 0.
 	\end{itemize}
 	By adding up the different parts, we see that $\tfrac32x^*-\frac12 \sum_{Q\in \Qscr} x^Q\le \mathbf{1}$ is already in the convex hull of $\{s,t\}$-tours.  
\qed
\medskip

We actually proved that  $\tfrac32x^*-\tfrac12 \sum_{Q\in \Qscr}x^Q$ {\em is a convex combination of $\{s,t\}$ tours, under the more general condition that  the narrow cuts are disjoint.} We can strengthen this result as follows. 
\begin{theorem}
Let $x^*$ be a feasible solution to the subtour elimination LP for $s-t$ path TSP, and let $G=(V, E)$ be the support graph of $x^*$. If no edge in $G$ is contained in more than two narrow cuts, then  $\tfrac32x^*$ is a convex combination of $\{s,t\}$-tours.
\end{theorem}
\prove
By Lemma~\ref{lem:chain}, we know that there exist $s\subseteq U_1\subset U_2\subset U_2\subset \ldots U_k$ such that the narrow cuts are exactly $\delta(U_i)$ for $i=1,\ldots, k$. We will call a narrow cut $Q=\delta(U_i)$ odd-numbered or even-numbered, depending on whether $i$ is odd or even.
We decompose $x^*$ into spanning trees.  However, we will now only remove lonely edges from either the odd-numbered narrow cuts, or the even-numbered narrow cuts, each with probability $\tfrac12$.
This changes the expectation of the forest to $x^*-\tfrac12\sum_{Q\in \Qscr}x^Q$. 


The upper bound $\tfrac12x^*+\tfrac12\sum_{Q\in \Qscr}x^Q$ on (PC) is still valid (see above), and we are again guaranteed that $2D_{F+J_F}=\emptyset$, since a bad edge can be contained in only two consecutive narrow cuts, and we never delete the lonely edges of both of these.  Whence the cost of reconnection is 0. Adding up the two nonzero contributions we get exactly $\frac32x^*$.
\qed




\subsection{A $3/2$-Approximation  if All Narrow Cuts Are Small}\label{subsec:32allsmall}
In this section we analyze the BOMD algorithm when all narrow cuts $Q$ have $x^*(Q)\le \frac32$.  
The following  inequality that appears in Vygen~\cite{Vygen15} is very handy to exploit such upper bounds, and gives an easier (but weaker) tool than the tools developed in Section~\ref{sec:doubling}  for bounding reconnection costs: 
\begin{equation} \hbox{For any $Q_1,Q_2\in\Qscr$, } x^*(Q_1\cap Q_2) \le \frac12(x^*(Q_1)+x^*(Q_2)) - 1.\label{eq:jens}\end{equation}


 We derive this by stopping before the last inequality in the proof of Claim~\ref{claim:cuts}, with the particular choice $\Qscr'=\{Q_1,Q_2\}$. Indeed, then $x^*(\cup_{Q\in\Qscr'} Q)\ge |\Qscr'|- 1 +\frac12(x^*(Q_1)+x^*(Q_2))=1+\frac12(x^*(Q_1)+x^*(Q_2)).$ Subtracting  this inequality from  $x^*(Q_1)+x^*(Q_2)=x^*(Q_1)+x^*(Q_2)$, we get (\ref{eq:jens}). 

\medskip 
In our special case  $x^*(Q_1\cap Q_2)\le \frac12$  follows  for all $Q_1,Q_2\in\Qscr$.

We show below that this inequality is sufficient to get a good bound on the cost of reconnection, assuming that we use a layered convex combination  from Section~\ref{sec:decomp}. 
In fact, we get the following simple analysis of the forest-based solutions found by the BOMD algorithm:
\begin{itemize}
	\item[] {\bf Forest}:  Forest $F:=F(S):= S\setminus L(S)$.
	
	{\em Expected Value of Forest}: $x^*-\sum_{Q\in \Qscr} x^Q$.
	
	\item[] {\bf Parity Correction}: The fractional solution $y_F$ in the $T_F\triangle \{s,t\}$-join polyhedron is constructed by adding the following vectors:
	\begin{enumerate}
		\item[] {\bf Basic Parity Correction} (BP): $\frac12x^*$.
		
		Note that  $\frac12 x^*(Q)\ge 1$ for any cut $Q$ that is {\em not} narrow, so (BP) is enough to ensure  that $y_F$ satisfies the constraints of the $T_F\triangle \{s,t\}$-join polyhedron for the cuts that are not narrow.
		
		{\em Expected Value of (BP)}: $\frac12x^*$.
		\item[] {\bf Parity Completion for Empty Cuts} (PCE): $\left(1-\frac{x^*(Q)}{2}\right)e_S^Q$.
		
		Note that (BP)+(PCE) are indeed sufficient to ensure that $y_F$ satisfies the constraints of the $T_F\triangle \{s,t\}$-join polyhedron for narrow cuts $Q$ such that $|Q\cap F|=0$. 
		
		{\em Expected Value of (PCE)}: $\sum_{Q\in \Qscr}\left(1-\frac{x^*(Q)}{2}\right)x^Q$.
		
		
		\item[] {\bf Parity Completion for Non-Empty Even Cuts} (PCL): $\frac12x^Q$.
		
		Recall from Section~\ref{sub:completion}  that indeed (BP) + (PCL) are indeed sufficient to ensure that $y_F$ satisfies the constraints of the $T_F\triangle \{s,t\}$-join polyhedron for narrow cuts $Q$ such that $|Q\cap F|$ is even and $\ge 2$. We also have that $\Pr(|Q\cap \Fscr|\ge 2)\le \Pr(|Q\cap \Sscr|\ge 2)\le x^*(Q)-1$, and thus:
		
		{\em Expected Value of (PCL)}: $\frac12\sum_{Q\in \Qscr} \left({x^*(Q)}-1\right)x^Q$.
	\end{enumerate}
	{\em Expected Value of Parity Correction:} $\frac12 x^* + \frac12\sum_{Q\in \Qscr} x^Q$.
	
	\item[] {\bf Reconnection}: 
	When all cuts are small, we can use a simple rule to implement reconnection (\ref{DF}): for each bad edge $b$ in $\Jscr_F$, we choose the ``leftmost'' of the lonely cuts $Q$ in $\Qscr(S,b)$ as the cut for which we do {\it not} add a doubled edge. (Cut $Q'=\delta(U')\in\Qscr$ is to the left of $Q=\delta(U)\in\Qscr$,  if  $s\in U'\subset U$; by Lemma~\ref{lem:chain} this is a total order on the narrow cuts.) 
	
	
	Now let  $Q\in \Qscr(S)$, and compute the probability of adding two copies of $e_S^Q$ for reconnection.  For this to happen, $\Jscr_F$ must contain an edge $b\in Q'\cap Q$ where $Q'$ is the first lonely cut in $S$ to the left of $Q$. The probability that $\Jscr_F$ contains such an edge is the sum of basic parity correction on  $Q'\cap Q$, plus parity completion on $Q'\cap Q$: the former of these two is at most $\frac{x^*(Q'\cap Q)}{2}\le \frac14$  by (\ref{eq:jens}) under our assumption that all cuts are small; the latter is $0$ by Lemma~\ref{lem:goodpcl}, since $\Sscr$ is layered and the parity completion vectors are scalar multiples of $x^Q$.  
	
	Hence, for a given $S$, we get a bound on the reconnection cost of $\frac12\sum_{Q\in \Qscr(S)}c(e_S^Q)$, that is:  
	
	{\em Expected Value of Reconnection Cost}: $\E{c(2D_{\Fscr+\Jscr_\Fscr})}\le \sum_{Q\in \Qscr}\frac12 c(x^Q)$.
	
\end{itemize}
We thus have that the total mean cost of $P_1(\Sscr)$ can be bounded by
\[\left(x^*-\sum_{Q\in \Qscr} x^Q\right) + \left(\frac12 x^* + \sum_{Q\in \Qscr} \frac12x^Q \right) + \sum_{Q\in \Qscr}\frac12 x^Q = \frac32 x^*.\]

\subsubsection*{One not-small narrow cut size}\label{subsub:one}
We can extend the above analysis to the case when there exists one value $z>\frac32$ such that for all narrow cuts $Q$, either $x^*(Q)\le \frac32$ or $x^*(Q)=z$. In this case, we let the parameter $\gamma$ in the basic parity correction vector be non-zero, where the exact value is determined by the analysis. Compared to the ratio $3/2$ we lose $1/34$, like in the general case!  


Now we use the same rule to deal with the tree $S$ in the event $b\in B(S)\cap\Jscr_F$: choose the leftmost lonely cut in $\Qscr(S,b)$ as the cut for which we do not use the edge $e_S^Q$ for reconnection. As in the case when all cuts are small (see the above proof), let $Q\in \Qscr(S)$ and consider the probability of using $e_S^Q$ for reconnection. Again, for this to happen, $\Jscr_F$ must contain an edge $b\in Q'\cap Q$ where $Q'$ is the first lonely cut in $S$ to the left of $Q$. The probability that $\Jscr_F$ contains such an edge is the sum of basic parity correction on  $Q'\cap Q$, plus parity completion on $Q'\cap Q$: the former of these two is now at most $\frac{x^*(Q'\cap Q)}{2}\le \frac12({x^*(Q)-1})$  by (\ref{eq:jens}); the latter is $0$ by Lemma~\ref{lem:goodpcl}, since $\Sscr$ is layered and the parity completion vectors are scalar multiples of $x^Q$. 

This is exactly the bound on the probability of adding two copies  of $e_S^Q$ shown for the general case in Section~\ref{sec:doubling}, but the proof is much simpler and combinatorial, it is ignoring Section~\ref{sec:doubling}!

For a given tree $S$, and its forest $F=S\setminus L(S)$, we can thus bound $\E{c(2D_{F+\Jscr_F})}\le \sum_{Q\in \Qscr(S)} (x^*(Q)-1) c(e_S^Q)$, and taking the average of all $S\in \Sscr$, we get a bound of $\sum_{Q\in \Qscr} (x^*(Q)-1)x^Q$.

 The remainder of the  computation is exactly the same as in Section~\ref{sec:ratio}.


We are not able to improve the obtained bound, even not  if  $z=\frac74$  and the only other cut-size is $1$ and occurs only for $\delta(s)$ and $\delta(t)$. Being able to reach in general the best bound we know for this easy case we reach the maximum within the possibilities of our methods.


\section{A Self-Contained Proof of the Extended K\H{o}nig-Hall Theorem}\label{app:KH}

In this section we give a self-contained proof of Claim~\ref{claim:KH} (see proof of Lemma~\ref{lem:feasibility}). 

We use the duality theorem of linear programming (instead of Farkas' Lemma), so we add the objective function $0$ to minimize. The dual of the LP defined by this objective function constrained by the inequalities ($D0$), ($D1$), ($D2$), is simple to state,
since every variable of the primal linear program is contained  with nonzero coefficients, in at most one inequality of ($D1$) and one inequality of ($D2$):

Denoting by $y_Q$ $(Q\in \Qscr (S) )$, $y_b$, $(b\in B(S))$ the dual variables associated to the inequalities in ($D1$), ($D2$) respectively, after multiplying ($D1$) by $-1$, the dual is:

\[\hbox{Maximize}  \sum_{Q\in\Qscr(S)}r_Qy_Q -\sum_{b\in B(S)}y_b, \hbox{  subject to:}\]

\[x^*(b)y_Q-y_b\le 0, \hbox{ and  $y_Q\ge0$,  $y_b\ge 0$ for all $b\in B(S), Q\in\Qscr(S,b)$.}\]
Clearly, the dual LP is feasible, and by the duality theorem of linear programming,  ($D0$), ($D1$), ($D2$) is feasible  if and only if the optimum of the dual LP is zero; furthermore, note that for  an arbitrary choice $y_Q\ge 0 (Q\in \Qscr(S))$, the optimal choice $y_b$ $(b\in B(S))$ is  uniquely determined as
\[y_b:=x^*(b)\max_{Q\in\Qscr(S,b)}y_Q\]

In other words ($D0$), ($D1$), ($D2$) is feasible, if and only if
\[\sum_{Q\in\Qscr(S)}r_Qy_Q \le\sum_{b\in B(S)}x^*(b)\max_{Q\in\Qscr(S,b)}y_Q, \mbox{ for all $y_Q\ge 0 (Q\in\Qscr')$.}\leqno{\rm (Farkas)}\]


\bigskip
Note that the condition of Claim~1 is exactly the  $y_Q:=1$ $(Q\in\Qscr')$ special case of (Farkas)!  So to prove Claim~1, we only have to check that whenever (Farkas) is violated the condition Claim~1 is also violated.

To prove this, suppose by contradiction that there exists $y_Q (Q\in \Qscr(S))$ be such that (Farkas) is violated, that is,
\[\sum_{Q\in\Qscr(S)}r_Qy_Q >\sum_{b\in B(S)}x^*(b)\max_{Q\in\Qscr(S,b)}y_Q, \leqno{\rm (violated Farkas)}\]
We suppose the number of different values of $y_Q$ is minimum here, and let $\eta=:\max\{y_Q: Q\in\Qscr\}$.
Note that if all $y_Q>0$ are equal (to $\eta$) then dividing all $y_Q$ $(Q\in\Qscr(S))$ by $\eta$, we see that Claim~1 is violated also.

If they are not all equal, let the second largest value of $y_Q$ be $\eta-\varepsilon$ with $\eta>\varepsilon>0$ and let $\Qscr'':=\{Q\in \Qscr(S): y_Q=\eta\}\subsetneq \Qscr',$. Now if the condition in Claim~1 is not violated then
\[ \sum_{Q\in \Qscr''} r_Q\le x^*(\cup_{Q\in\Qscr''} Q\cap B(S) ).\]
Subtracting $\varepsilon$ times the left hand side of this inequality from (violated Farkas), it is straightforward to see that (as usual, with $y_b:=x^*(b)\max_{Q\in\Qscr(S,b)}$ $\varepsilon$ the right hand side of (violated Farkas) is also decreased by at least $\varepsilon$ times the right hand side. We get that (Farkas) is violated with one fewer $y_Q$ value, a contradiction, finishing the proof of the claim.

\section{Matroids}\label{sec:matroids}
We discuss here a slightly different way of handling layered convex combinations  by using basis packing  rather than  the matroid partition approach of  Section~\ref{sec:decomp}. These two are well-known to be equivalent, but both may have their advantage at use.  An  advantage of basis packing for us is that it helps presenting  a partial direct proof of Theorem~\ref{thm:layered}, and measure what is missing for a full proof in a clean way; see Section~\ref{sub:basispacking}).  In the second subsection, we show a new matroid construction generalizing the matroids of  
Section~\ref{sec:decomp}, which may provide some additional insight.

\subsection{How to Check for Basis Packing, and What Is Missing?}\label{sub:basispacking}

We state  here  a version of the ``Basis Packing Theorem'' of Edmonds for graphs. This provides some insight to the graphs induced by the level sets of the layers, implying a somewhat weaker statement than the layered convex combination of spanning trees, and making clear what is missing from  a full  direct proof (as promised in Section~\ref{sec:decomp}). 


For a given vector $w$ to be a convex combination of spanning trees is  the $\zeta=1$ special case of the following well known result of Tutte \cite{Tutte61} and Nash-Williams \cite{NW61}  about packing spanning trees in graphs, itself a special case of matroid partition. This is a fractional  (so weaker) version  \cite[Theorem 51.1a]{Schrijver-book}:

For family $\Pscr$ of disjoint subsets of $V$, let $\delta (\Pscr)$  denote the set of edges in $E$ whose two endpoints are in two different sets of $\Pscr$.  

\begin{theorem}\label{thm:basispacking}
	Let $G=(V,E)$ be a graph, $\Bscr$ the set of its spanning trees, $w\in\mathbb{R}^E$, and $\zeta\in\mathbb{R}_+$. There exist $\lambda_B\in\mathbb{R}_+$ ($B\in\Bscr$, $|\{B\in\Bscr:\lambda_B >0\}|\le|E|$) such that:
	\begin{equation}
	\sum_{B\in\Bscr}\lambda_B B\le w,\, \sum_{B\in\Bscr}\lambda_B = \zeta,
	\label{concl:basispacking}
	\end{equation}
	\begin{equation}
	\hbox{if and only if for any partition $\Pscr$ of $V$:\quad} w(\delta (\Pscr) )\ge \zeta (|\Pscr| -1),\label{cond:basispacking}
	\end{equation}
	and $\lambda_B$ $(B\in\Bscr)$ or a violated condition can be found in strongly polynomial time.
\end{theorem}

We  prove that for all $i=1,\ldots,k$ (\ref{concl:basispacking}) holds for  $\Bscr:=\Bscr_i$ and  $\zeta=\zeta_1+\ldots+\zeta_i$, and we can actually go to the furthest possible statement in this direction.  For each basis in the chain $\Bscr_1\subseteq\ldots\subseteq \Bscr_k$ this graph version of the basis packing theorem is exactly what we need. 

Still, we also state basis packing theorem for matroids  whose condition would be equivalent to check to that of Theorem~\ref{thm:matroidpartition}: 

\begin{theorem}\label{thm:matroidbasispacking}
	Let $M_i=(E,r_i)$ $(i=1,\ldots,k)$ be matroids, $w\in\mathbb{R}^E$,
	$R:=r_1(E)=\ldots=r_k(E)=x^*(E)$,  and $\lambda_i\in \mathbb{R}$, $0\le \lambda_i\le 1$ $(i=1,\ldots,k)$.
	Let $P^i$ the convex hull of $\Bscr_i$ the set of bases of $M_i$.
	There exist $x^i\in P^i$ for $i=1,\ldots, k$ such that:
	\begin{equation}
	\sum_{i=1}^k\lambda_ix^i=w,\, \label{concl:matroidbasispacking}
	\end{equation}
	\begin{equation}
	\hbox{if and only if for all $X\subseteq E:$ $w(X)\ge \sum_{i=1}^k\lambda_i(R-r_i(X)).$}
	\label{cond:matroidbasispacking}
	\end{equation}
	and the coefficients of a convex combination or a violated condition can be found in strongly polynomial time.
\end{theorem}

This is the fractional version of \cite{Edm65} \cite[Corollary 42.1d]{Schrijver-book}, a generalization of Theorem~\ref{thm:basispacking} for arbitrary matroids.  A natural condition to check would be  the condition of this theorem for our matroids.  
  However, this appears to be a somewhat confusing task that we could not fully solve so far. 

\begin{lemma}\label{lem:disGao} For each $i=1,\ldots k$, $\Bscr_i$ satisfies (\ref{concl:basispacking}) with $w:=x^*$, and $\zeta:=\zeta_1+\ldots + \zeta_i$.
\end{lemma}


\prove It is necessary and sufficient to check two inequalities: (\ref{cond:basispacking}) for the graphs induced by level-sets of $\Qscr_i$ and  $x^*(Q)\ge \zeta_1+\ldots + \zeta_i$ for cuts $Q\in\Qscr_i$.  Then we get by  Theorem~\ref{thm:basispacking}  a ``packing'' of $\zeta$ spanning trees in the level sets, and the same quantity of edges in the cuts of $\Qscr_i$;  these can be straightforwardly pasted together to get the claimed  packing. Both  inequalities are consequences of the following claim:

\medskip\noindent{\bf Claim}: Let $\Pscr$ be a partition of $W\setminus U\ne\emptyset$ where $s\in U\subseteq W$,  $Q=\delta(U)$, $R=\delta(W)$, $x^*(Q),x^*(R)\le 2-\zeta$.
Then $x^*_{W\setminus U} (\delta(\Pscr)) \ge \zeta (|\Pscr|-1)$, where  $x^*_{W\setminus U}$ is a restricton of $x^*$ to the set of edges induced by $W\setminus U$.

\smallskip
Indeed, applying the submodular inequality (\ref{eq:submodularity}) to $W$ and $V\setminus U$:
\begin{equation}
2(2-\zeta) \ge x^*(Q) + x^*(\delta (R)\ge x^*(\delta (W\setminus U)), \label{eq:subQR}
\end{equation}
where $x^*(\delta (W\setminus U))=\sum_{P\in\Pscr}x^*(\delta(P)) - 2 x^*_{W\setminus U}(\delta(\Pscr))\ge 2 |\Pscr| - 2 x^*_{W\setminus U}(\delta(\Pscr))$. Substituting this into (\ref{eq:subQR}) we obtain:
\begin{equation}\label{eq:strong}
x^*_{W\setminus U}(\delta(\Pscr))\ge |\Pscr| - 2 + \zeta .
\end{equation}
Now if  $|\Pscr|=2$ this is exactly the claimed inequality, and in case $|\Pscr|>2$ it is stronger. The claim is proved.

Now the Lemma also follows by noting that in case of $Q,R\in\Qscr_i$, the condition of the Claim is satisfied with
$\zeta:=\zeta_1+\ldots + \zeta_i$.  Moreover, if $U$ and $W$ are in addition such that there exists exactly one $Y$ such that $U\subsetneq Y\subsetneq W$, $\delta(Y)\in \Qscr_i$, then apply the claim to the partition of size $2$ $\{Y\setminus U\}$, to get $x^*(L_i\cap \delta (Y))\ge \zeta$, with the same $\zeta$.

Pasting together  the $\zeta$ spanning trees of inclusionwise minimal level sets of $\Qscr_i$ and of the $\zeta$ edges in $L_i\cap Q$ for each $Q\in\Qscr_i$ provides the packing of $\zeta$  bases. 
\qed

\medskip
Note that  $|\Pscr| - 2 + \zeta= \zeta(|\Pscr| - 1) + (1-\zeta)(|\Pscr| - 2)$.  With this remark (\ref{eq:strong})  and Theorem~\ref{thm:matroidbasispacking} straightforwardly imply the following stronger result:  

\begin{theorem}\label{thm:maxproved} For every $i=1,\ldots k$ there exists a convex combination of forests majorated by $x^*$ consisting of a packing of
	$\zeta=\zeta_1+\ldots+\zeta_i$ spanning trees that are bases of $M_i$ and $\zeta_{i+1}+\ldots+\zeta_k$ forests, each with at most two components induced in each level set of $M_i$. 
\end{theorem}

Such a convex combination is the best possible in terms of  spanning trees and graphs with at most two components in each level set. However, we do not know how to use this sharpening to have all the packings simultaneously. 


 Recall $\Bscr_1\subseteq\ldots\subseteq \Bscr_k$. A convex combination of spanning trees containing simultaneously  all the packings of Theorem~\ref{thm:maxproved} is exactly the assertion of Lemma~\ref{lem:equivalent} (ii), and as such, by Lemma~\ref{lem:equivalent} is equivalent to the existence of a layered convex combination. Unfortunately, Theorem~\ref{thm:maxproved} is weaker than (iii).


\subsection{A (New?) Matroid Construction }

We present the matroid construction of Section~\ref{sec:decomp} starting from an arbitrary matroid.  Is this matroid construction known? The graph special case was very useful for us, and the matroidal proofs may provide some more insight.


A {\em cut} in a matroid is a minimal set that does not intersect any circuit in exactly $1$ element; a set of elements is a cut if and only if it is a circuit of the dual matroid. A matroid will be given in the form $M=(E,\Bscr)$ or in the form $(M,r)$ where $\Bscr$ is the set of its bases, and $r$ is its rank function.

\begin{lemma}\label{lem:matroid} Let $M=(E,\Bscr)$ be a matroid, and $\Cscr$ a set of cuts of $M$ such  that
	\[\Bscr_\Cscr:=\{B\in\Bscr: |B\cap C|\le 1 \hbox{ for all $C\in\Cscr$}\}\ne\emptyset.\]
	Then $\Bscr_\Cscr$ is the set of bases of a matroid.
\end{lemma}

It follows immediately that then in fact $|B\cap C|= 1$ (for all $B\in\Bscr_\Cscr, C\in\Cscr$); it follows from $\Bscr_\Cscr\ne\emptyset$ that each $C\in\Cscr$ has elements that are not contained in any other member of $\Cscr$. (Hint: If $b\in B\in\Bscr$, then there exists a unique cut in $M$ disjoint of $B\setminus \{b\}$.)

\medskip
\prove Let $B_1,B_2\in\Bscr_\Cscr$, $b_2\in B_2\setminus B_1$ arbitrary. We show there exists $b_1\in B_1$ such that
$(B_1\setminus \{b_1\})\cup \{b_2\}\in \Bscr_\Cscr$.


If  $b_2\in \cup_{C\in\Cscr}C$, then let  $C$ be the (unique)
cut disjoint of $B_2\setminus b_2$; then $C\in\Cscr$. But then the unique circuit of $B_1\cup \{b_2\}$ must have an element in $C$ besides $b_2$, denote it $b_1$. (Since $B_1\setminus \{b_1\}$ has also a unique disjoint cut, $C$ is the only cut of $\Cscr$ containing $b_1$.) So $(B_1\setminus \{b_1\})\cup \{b_2\}\in \Bscr_\Cscr$.

If $b_2\notin \cup_{C\in\Cscr}C$, then the unique circuit of $B_1\cup \{b_2\}$ is disjoint of $\cup\Cscr$, since a circuit and a cut cannot meet in exactly $1$ element. Let $b_1\ne b_2$ be an element of this circuit.
\qed




\end{document}



1604.02486.extracted_bib
{AnKS12 H.~Ch.~An, R.~D.~Kleinberg, and D.~B.~Shmoys. \newblock Improving Christofides' algorithm for the s-t path {TSP. \newblock In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC'12). \newblock Revised in \cite{AnKS12bis.
1604.02486.extracted_bib
{AnKS12bis H.~Ch.~An, R.~D.~Kleinberg, and D.~B.~Shmoys. \newblock Improving Christofides' algorithm for the s-t path {TSP. \newblock {\em J. {ACM, 62(5):34, 2015.
1604.02486.extracted_bib
{Barahona95 F.~Barahona. \newblock Packing spanning trees. \newblock {\em Mathematics of Operations Research, 20(1):104--115, 1995.
1604.02486.extracted_bib
{CheriyanFG15 J.~Cheriyan, Z.~Friggstad, and Z.~Gao. \newblock Approximating minimum-cost connected t-joins. \newblock {\em Algorithmica, 72(1):126--147, 2015.
1604.02486.extracted_bib
{Christofides76 N.~Christofides. \newblock Worst case analysis of a new heuristic for the traveling salesman problem. \newblock Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.
1604.02486.extracted_bib
{Cook11 W.~J.~Cook. \newblock {\em In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. \newblock Princeton University Press, December 2011.
1604.02486.extracted_bib
{Cunningham84 W.~Cunningham. \newblock Testing membership in matroid polyhedra, \newblock {\em Journal of Combinatorial Theory, Series B, 36:161--188, 1984.
1604.02486.extracted_bib
{DantzigFJ54 G.~Dantzig, R.~Fulkerson, and S.~Johnson. \newblock Solution of a large-scale traveling-salesman problem. \newblock {\em Operations Research, 2:393--410, 1954.
1604.02486.extracted_bib
{Edm65 J.~Edmonds. Lehman's switching game and a theorem of Tutte and Nash-Williams, {\em J. of Research of the National Bureau of Standards, Section B 69 (1965), pp.\ 125--130.
1604.02486.extracted_bib
{Edm70 J.~Edmonds. Submodular functions, matroids and certain polyhedra. {\em In: Combinatorial Structures and Their Applications, Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications 1969 (R.~Guy, H.~Hanani, N.~Sauer, J.~Sch\"onheim, eds.), Gordon and Breach, New York 1970, pp.\ 69--87.
1604.02486.extracted_bib
{EdmJ73 J.~Edmonds, and E.~L.~Johnson. Matching, Euler tours and the Chinese postman. {\em Mathematical Programming, 5 (1973), 88--124.
1604.02486.extracted_bib
{Fra11 A. Frank. Connections in Combinatorial Optimization. Oxford University Press 2011.
1604.02486.extracted_bib
{Gao13 Z.~Gao. \newblock An {LP-based 3{/2-approximation algorithm for the {s-{t path graph {Traveling {Salesman {Problem. \newblock {\em Oper. Res. Lett., 41(6):615--617, 2013.
1604.02486.extracted_bib
{Gao15 Z. Gao. \newblock On the metric s-t path traveling salesman problem. \newblock {\em {SIAM J. Discrete Math., 29(3):1133--1149, 2015.
1604.02486.extracted_bib
{GarJT76 M.~R.~Garey, D.~S.~Johnson, and R.~E.Tarjan. \newblock The planar hamiltonian circuit problem is np-complete. \newblock {\em SIAM Journal on Computing, 5(4):704--714, 1976.
1604.02486.extracted_bib
{GottschalkV15 C.~Gottschalk and J.~Vygen. \newblock Better {s-{t -tours by Gao trees. \newblock {\em CoRR, abs/1511.05514, 2015.
1604.02486.extracted_bib
{Hoogeveen91 J.~A.~Hoogeveen. \newblock Analysis of Christofides' heuristic: Some paths are more difficult than cycles. \newblock {\em Operations Research Letters, 10(5):291 -- 295, 1991. %
1604.02486.extracted_bib
{JohnsonP85 % D.~S.~Johnson and C.~H.~Papadimitriou. % \newblock Performance guarantees for heuristics, in: % \newblock {\em The Traveling Salesman Problem -- A Guided Tour of Combinatorial Optimization (E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, eds.) Wiley, Chichester, 1985, pp. 145 -- 180.
1604.02486.extracted_bib
{NW61 C.St.J.A.~Nash-Williams. \newblock Edge-disjoint spanning trees of finite graphs, \newblock {\em The Journal of the London Mathematical Society, 36, 445--450, 1961.
1604.02486.extracted_bib
{Schrijver-book A.~Schrijver. \newblock {\em Combinatorial Optimization - Polyhedra and Efficiency. \newblock Springer, 2003.
1604.02486.extracted_bib
{Sebo13 A.~Seb\H{o. \newblock Eight-fifth approximation for the path {TSP. \newblock In {\em Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 362--374, 2013.
1604.02486.extracted_bib
{SV A.~Seb\H{o, J.~Vygen, Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs, {\em Combinatorica, {34 (5) October (2014), 597--629.
1604.02486.extracted_bib
{Sebo14 A.~Seb{\H{o. \newblock Problems about uniform covers, with tours and detours. \newblock In {\em Matematisches Forschungsinstitut Oberwolfach Report No.~51/2014, DOI: 10.4171/OWR/2014/51, November 2014, on joint work with Y.~Benchetrit and M.~Stehl\'\i k, pages 2912--2915, March 2015.
1604.02486.extracted_bib
{Tutte61 W.T.~Tutte. \newblock On the problem of decomposing a graph into $n$ connected factors, \newblock {\em The Journal of the London Mathematical Society, 36, 221-230, 1961.
1604.02486.extracted_bib
{Vygen15 J.~Vygen. \newblock Reassembling trees for the traveling salesman. \newblock {\em CoRR, abs/1502.03715, 2015.
1604.02486.extracted_bib
{Wolsey80 L.~A.~Wolsey. \newblock Heuristic analysis, linear programming and branch and bound. \newblock {\em Mathematical Programming Study, 13:121--134, 1980.