## 5 Performance Guarantee  
Let \(x^{*}\) be the vector minimizing \(\sum_{e\in A}c_{e}x_{e}\) over DToC(\(G\)) and \(U=\{v\in V\,|\,x^{*}(\delta^{+}(\{v\}))\geq\frac{1}{2}\}\). Let \(y^{*}=2x^{*}\), and let \(k\) be the minimum integer such that \(ky^{*}\) is integer. Let \(\tilde{G}=(V,\tilde{A})\) be the multi-graph that has \(ky^{*}_{e}\) copies of arc \(e\) for each \(e\in\tilde{A}\). Note that \(\tilde{G}\) is Eulerian. For any \(i\
eq j\in V\), let \(p_{\tilde{G}}(i,j)\) be number of disjoint paths from \(i\) to \(j\) in \(\tilde{G}\).  
**Remark 2**: \(p_{\tilde{G}}(u,j)\geq k\) _for all \(u\in U\) and \(j\in V\setminus\{u\}\)._  
_Proof._ To prove the remark, we will show that for any \(S\subset V\) such that \(u\in S\) and \(j\in V\setminus S\), we have \(|\delta^{+}_{\tilde{G}}(S)|\geq k\). Indeed, if \(A(S)\
eq\emptyset\) then by construction, \(x^{*}(\delta^{+}_{\tilde{G}}(S))\geq\frac{1}{2}\) which implies \(y^{*}(\delta^{+}_{\tilde{G}}(S))\geq 1\) and consequently \(|\delta^{+}_{\tilde{G}}(S)|\geq k\). Otherwise, if \(A(S)=\emptyset\) then \(x^{*}(\delta^{+}_{\tilde{G}}(S))\geq x^{*}(\delta^{+}(u))\geq\frac{1}{2}\). Equivalently, \(y^{*}(\delta^{+}_{\tilde{G}}(S))\geq y^{*}(\delta^{+}(u))\geq 1\). Hence, we also have \(|\delta^{+}_{\tilde{G}}(S)|\geq k\).  
In \(\tilde{G}\), for each \(i\in V\setminus U\), repeat the splitting operation on \(i\) until \(d^{+}_{\tilde{G}}(i)=d^{-}_{\tilde{G}}(i)=0\). Consequently, after these operations, all the arcs in \(\tilde{G}\) having the end-nodes in \(U\). Let \(\tilde{G}_{U}=(U,\tilde{A}_{U})\) be the subgraph of induced by \(U\) of \(\tilde{G}\).  
**Remark 3**: _After these splitting operations, \(p_{\tilde{G}_{U}}(u,v)\geq k\) for all \(u\in U\) and \(v\in U\setminus\{u\}\)._  
Consider the graph \(G_{U}=(U,A_{U})\) that is defined in Step **(2)** of the algorithm. Note that all the arcs in \(\tilde{A}_{U}\) (with eventually multiple copies) are in \(A_{U}\) but there may exist arcs in \(A_{U}\) that are not in \(\tilde{A}_{U}\). Let \(x^{U}\) be the vector in \(\mathbb{R}^{|A_{U}|}\) such that for each \(e\in A_{U}\), \(x^{U}_{e}=\frac{p_{e}}{k}\), where \(p_{e}\) is the number of copies of \(e\) in \(\tilde{A}_{U}\) (\(p_{e}=0\) if \(e\
otin\tilde{A}_{U}\)).  
**Lemma 4**: _We have \(2 cx^{*}=cy^{*}\geq c^{U}x^{U}\)._  
_Proof._ We have seen that \(kx^{U}\) is obtained from \(ky^{*}\) by repeated splitting operations on the vertices in \(V\setminus U\). By definition of \(c^{U}\) which takes the shortest path cost, we have \(c^{U}(kx^{U})\leq c(ky^{*})\) which implies \(c^{U}x^{U}\leq cy^{*}=2 cx^{*}\).  
Let \(z^{*}\) be an optimal solution of Held-Karp relaxation over \(G_{U}\).  
**Lemma 5**: \(c^{U}x^{U}\geq c^{U}z^{*}\)_._  
_Proof._ We can see that \(x^{U}\) satisfies the following linear inequalities  
\[x(\delta^{+}_{G_{U}}(u))=x(\delta^{-}_{G_{U}}(u))\]  
\[x(\delta^{+}_{G_{U}}(S))\geq 1\mbox{ for all }\emptyset\subset S\subset U\]  
which are the inequalities of (5) applied to \(G_{U}\). By Theorem 2, \(z^{*}\) minimizes the cost function \(c^{U}x\) over (5). Hence we have \(c^{U}x^{U}\geq c^{U}z^{*}\).  
We are ready now to state the main theorem  
**Theorem 3**: _The algorithm outputs a directed tour cover of cost no more than \(2\log_{2}(n)\) times the cost of the minimum directed tour cover._  
_Proof._ The algorithm return, as a solution of DToCP, the traveling salesman directed tour output \(T\) by [PERSON] _et al._'s heuristic applied on \(G_{U}\). Let \(x^{T}\) be its incidence vector. The cost of \(T\) is then equal to \(c^{U}x^{T}\). [PERSON] [5] proved that the cost of \(T\) is not more than \(\log_{2}(n)\) times the cost of the optimal solution of Held-Karp relaxation over \(G_{U}\), _i.e._, \(c^{U}x^{T}\leq\log_{2}(n)c^{U}z^{*}\). By Lemmas 5 and 4, we have \(c^{U}x^{T}\leq 2\log_{2}(n)cx^{*}\).