Approximability of TSP on Power Law Graphs\\[1ex]
Mikael Gast\thanks{Dept. of Computer Science and the Hausdorff Center for Mathematics
University of Bonn. e-mail:{ \href{mailto:gast@cs.uni-bonn.de
Mikael Gast\thanks{Dept. of Computer Science
University of Bonn. % e-mail:{ \tt gast@cs.uni-bonn.de
In this paper we study the special case of Graphic TSP where the underlying graph is a power law graph (PLG). We give a refined analysis of some of the current best approximation algorithms and show that an improved approximation ratio can be achieved for certain ranges of the power law exponent $\beta$. For the value of power law exponent $\beta=1.5$ we obtain an approximation ratio of $1.34$ for Graphic TSP. % and inapproximability bound of $1.0001$ for the Graphic TSP. Moreover we study the $(1,2)$-TSP with the underlying graph of $1$-edges being a PLG. We show improved approximation ratios in the case of underlying deterministic PLGs for $\beta$ greater than $1.666$. %certain ranges of the power law exponent. For underlying random PLGs we further improve the analysis and show even better expected approximation ratio for the range of $\beta$ between $1$ and $3.5$. %$2<\beta<3.5$. On the other hand we prove the first explicit inapproximability bounds for $(1,2)$-TSP for an underlying power law graph.
Approx.tex

\section{Graphic TSP on Power Law Graphs}\label{sec:GraphicTSP}
In this section we consider the Graphic TSP in power law graphs. Given a connected graph $G=(V,E)$ with $n$ vertices, the Graphic TSP asks for a minimum cost tour 
on the vertices with respect to the shortest path metric induced by $G$.
This is a natural special case of the general TSP and it was shown that an improvement of the approximation algorithm of Christofides' algorithm can be achieved.
The first small improvement is due to \citeauthor{Gharan2011} \cite{Gharan2011} who showed a $(\frac{3}{2}-\varepsilon)$-approximation (for an $\varepsilon$ in the order of $10^{-12}$) based on a refined analysis of Christofides' algorithm for Graphic instances.
A whole different approach is due to \citeauthor {Moemke2011} \cite{Moemke2011} where the starting point is a $2$-vertex connected graph which is made Eulerian by removing edges. This approach yields an approximation ratio of $\frac{14(\sqrt{2}-1)}{12\sqrt{2}-13}<1.461$ which was subsequently improved by \citeauthor{Mucha2012} \cite{Mucha2012} to a ratio of $\frac{13}{9}\approx 1.444$.
The current best approximation ratio of $\frac{7}{5}$ is achieved by \citeauthor{Sebo2014} \cite{Sebo2014}.

Here we consider the special case of Graphic TSP when the underlying graph $G$ is an $(\alpha,\beta )$-PLG.
We show that---for certain ranges of the parameter $\beta$---a refined analysis of the above algorithms yield better approximation ratios in this case.
Our results hold for $1<\beta<2.479$, namely when $\zeta(\beta-1)>2\cdot\zeta(\beta)$.
For $\zeta(\beta-1)\leq 2\cdot\zeta(\beta)$, $(\alpha,\beta)$-PLGs are not connected anymore.

\subsection{Improved Analysis}
We start by slightly improving the analysis of the basic $2$-approximation algorithm for TSP applied on instances of Graphic TSP with an underlying $(\alpha,\beta )$-PLG.
For the general TSP instances, a $2$-approximation can easily be achieved by the so called \emph{MST heuristic}. In order to construct a tour one computes a 
\emph{minimum spanning tree} (MST) of $G$ and replaces each edge of the tree by a pair of parallel edges. The resulting multigraph is Eulerian, and making use of triangle inequality,
an Euler tour can be transformed into a traveling salesman tour. 
Since any tour is connected and thus contains a spanning tree, a MST has cost at most half of the optimum tour. %This is the so called \emph{MST heuristic}.
For the case of an underlying $(\alpha,\beta )$-PLG the cost of an MST is $\zeta (\beta)e^{\alpha}-1$, while every tour has cost at least 
$\zeta (\beta)e^{\alpha}+\frac{e^{\alpha}}{2}$. This lower bound holds since $G$ contains $e^{\alpha}$ nodes of degree $1$. 
As we shall see below in the analysis of Christofides' algorithm on PLGs, we also have $c(\tau )\geq 2e^{\alpha}$ for every tour $\tau$.
Thus we obtain the following result.
\begin{lemma}
For $1<\beta<2.48$, the approximation ratio of the MST heuristic for $(\alpha,\beta)$-Power Law Graphic TSP is bounded by 
$\frac{2\zeta (\beta)}{\max\{2,\zeta (\beta)+\frac{1}{2}\}}$.
\end{lemma}  
Now we consider the performance of Christofides' algorithm \cite{Christofides1976} on power law Graphic instances. On general instances, 
this algorithm constructs an MST $T$ and a minimum cost perfect matching $M$ on the subset
of nodes which have an odd degree in $T$. If $\tau^*$ denotes an optimum TSP tour, then $c(M)\leq c(\tau^*)$ and $c(M)\leq c(\tau^*)\slash 2$, which yields the 
approximation ratio of $1.5$ for the general Metric TSP. Now we will improve this bound for the special case of $(\alpha,\beta)$-Power Law Graphic TSP when $\beta >1$. 
Again the MST cost is $c(T)=\zeta (\beta)e^{\alpha}-1\leq c(\tau^*)$. The problem now is that we do not know in advance if the matching cost $c(M)$ is close to $c(T)$
or close to $\frac{1}{2}c(T)$. 

Our approach is to charge at least some part of the matching cost in order to get an improved approximation ratio. First we observe that all degree $1$ nodes in $G$ 
have an odd degree in $T$. Thus we obtain that 
\[c(M) = e^{\alpha} +(c(M)-e^{\alpha}) \leq e^{\alpha} +\left (\frac{c(\tau^*)}{2}-e^{\alpha}\right ),\]
from which we also conclude that $c(\tau^* )\geq 2e^{\alpha }$. Moreover, $c(\tau^*)\geq (\zeta (\beta )+\frac{1}{2})e^{\alpha}$.
Hence the approximation ratio is bounded by
\[\frac{\zeta (\beta)e^{\alpha}+c(M)}{c(\tau^*)}\leq\frac{\zeta (\beta)e^{\alpha}+\frac{c(\tau^*)}{2}}{c(\tau^*)}
\leq\frac{1}{2}+\frac{\zeta (\beta)}{\max\{2,\zeta (\beta)+\frac{1}{2}\}}\]
We have shown the following result.
\begin{lemma}
For $1<\beta<2.48$, the approximation ratio of Christofides' algorithm on $(\alpha,\beta)$-power law Graphic instances is at most 
$\frac{1}{2}+\frac{\zeta (\beta)}{\max\{2,\zeta (\beta)+\frac{1}{2}\}}$.
\end{lemma}
Now we consider the M{\"o}mke-Svensson algorithm for TSP \cite{Moemke2011}. It is based on the notion of {\sl removable pairings}. A {\sl removable pairing} $(R,{\mathcal P})$
consists of a subset of edges $R\subseteq E$ and a subset ${\mathcal P}\subseteq P(E)$ of the power set of $E$ such that ${\mathcal P}=\{P_v|v\in U\}$ for some subset
$U\subseteq V$, each $v\in U$ has degree at least $3$ and $P_v$ is a set of two edges incident to $v$. The sets in ${\mathcal P}$ have to be pairwise disjoint. Moreover,
for each subset $F\subseteq R$ such that for each $v\in U$, $F$ contains at most one element from $P_v$, the graph $(V,E\setminus F)$ is connected.

\citeauthor{Moemke2011} \cite{Moemke2011} show that, given a removable pairing $(R,{\mathcal P})$, one can construct in polynomial time a tour $\tau$ of cost 
$c(\tau )\leq \frac{4}{3}c(E)-\frac{2}{3}c(R)$. This yields an approximation ratio of $\frac{4}{3}$ for Subcubic Graphic TSP, i.e. Graphic TSP in graphs of maximum degree
at most $3$. We now analyse the performance of this algorithm for Power Law Graphic TSP for $\beta >2$. Note that for $\beta\leq 2$ the M{\"om}ke-Svensson bound 
is not applicable, since the cardinality of $E$ is not linear in $|V|$ anymore. In the case $\beta >2$, we use our lower bound
$c(\tau^*)\geq\max\{2,\zeta (\beta)+\frac{1}{2}\}\cdot e^{\alpha}$. We apply the M{\"o}mke-Svensson algorithm to every $2$-vertex connected component of the
graph $G=(V,E)$. Suppose first that the subgraph $G'=(V',E')$ induced by the vertices of degree at least $2$ is $2$-vertex connected.
Now we have to give a bound on the size of the set $R$, where $(R,{\mathcal P})$ is a removable pairing
used in the algorithm. This is constructed as follows. Choose a root $v\in V$ and let $(V,S)$ be a DFS tree in $G'$ rooted at $r$. Initially, $R\colon =E\setminus S$
and ${\mathcal P}=\emptyset$. Then 
the vertices $v\in V$ are processed in any order. For each such $v$, if $v$ has degree at least $3$, is incident to some edge $e=\{v,w\}\in E\setminus S$ such that 
$v$ is on the $r-w-$path in $(V,S)$, $e'$ is the first edge on the subpath from $v$ to $w$ and $e'$ has not yet been added to $R$, then add $e'$ to $R$ and $\{e,e'\}$ to 
the set ${\mathcal P}$.

First we observe that in the case $\beta >2$, 
\begin{align*}
|E'\setminus S| & \geq  |E|-|\{v|\text{deg}(v)=1\}|-(|V'|-1)\\
                & \geq  \frac{1}{2}\zeta (\beta -1)e^{\alpha} - e^{\alpha}- (\zeta (\beta)-1)e^{\alpha}
                 =      \left(\frac{1}{2}\zeta (\beta -1)-\zeta (\beta)\right)e^{\alpha} 
\end{align*}  
Given an edge $e\in E'\setminus S$ with $e=\{v,w\}$ such that $v$ lies on the $r-w-$path in the DFS tree, then $v$ is called the root of the edge $e$.
Since each such root gives rise to at least one additional edge in the set $R$, we will now give a lower bound on the number of roots needed to cover all
the edges in $E'\setminus S$. Each root $v\in V'\setminus\{r\}$ has degree at least $2$ plus the number of edges $e\in E'\setminus S$ with root $v$.

The volume of a set of nodes is defined as the sum of their node degrees. In Power Law Graphs, in the case $\beta >2$ the volume of a node degree interval
$[x\Delta,\Delta ]=\{v|x\Delta\leq\text{deg}(v)\leq\Delta\}$ can be estimated as follows:
\begin{align*}
\text{vol}([x\Delta,\Delta ]) & = \sum_{i=x\Delta}^{\Delta}\left\lfloor\frac{e^{\alpha}}{i^{\beta}}\right\rfloor\cdot i
    \leq \sum_{i=x\delta}^{\Delta}\frac{e^{\alpha}}{i^{\beta-1}}
    \leq e^{\alpha}\int_{x\Delta}^{\Delta +1}\frac{1}{x^{\beta -1}}dx + (1-x)\Delta\\ &= (1+o(1))e^{\alpha} \left [\frac{y^{2-\beta}}{2-\beta}\right ]_{x\Delta}^{\Delta +1}
    = \frac{(1+o(1))\e^{\alpha}}{\beta -2}\left (\frac{1}{(x\Delta)^{\beta -2}}-\frac{1}{(\Delta +1)^{\beta -2}}\right ) \\
     &\leq   \frac{e^{\alpha-\alpha\cdot\frac{\beta-2}{\beta}}}{(\beta -2)\cdot x^{\beta -2}}
     =      \frac{e^{2\alpha\slash\beta}}{(\beta -2)x^{\beta -2}}
\end{align*} 	
The volume available for edges $e\in E'\setminus S$ is 
\[\sum_{i=x\Delta}^{\Delta}\left\lfloor\frac{e^{\alpha}}{i^{\beta}}\right\rfloor (i-2)\leq \frac{e^{2\alpha\slash\beta}}{(\beta -2)x^{\beta -2}}-2(1-x)\Delta\]
Now this volume has to cover the set $E'\setminus S$, i.e.
%\[\begin{array}{c@{\quad}r@{}c@{}l}
\begin{align*}
   \frac{e^{2\alpha\slash\beta}}{(\beta -2)x^{\beta -2}}-2(1-x)\Delta & \geq \left(\frac{1}{2}\zeta (\beta -1)-\zeta (\beta)\right)e^{\alpha}\shortintertext{which holds if and only if}
   \frac{e^{2\alpha\slash\beta}}{(\beta -2)x^{\beta -2}} & \geq (1+o(1))\cdot \left(\frac{1}{2}\zeta (\beta -1)-\zeta (\beta)\right)e^{\alpha}
 \end{align*}
%\end{array}\]
Hence we have to choose 
\[x\leq\frac{e^{-\alpha\slash\beta}}{((\beta -2)(\frac{1}{2}\zeta (\beta -1)-\zeta (\beta)))^{1\slash (\beta -2)}} \]
Then the size of the set $[x\Delta,\Delta ]$ is
\begin{align*}
\sum_{x\Delta}^{\Delta}\left\lfloor\frac{e^{\alpha}}{i^{\beta}}\right\rfloor & \geq e^{\alpha}\cdot\frac{(x\Delta)^{1-\beta}-(\Delta +1)^{1-\beta}}{\beta -1}-\Delta\\
  & \geq (1-o(1))\frac{e^{\alpha}}{(\beta -1)}\cdot \left [(\beta -2)\left(\frac{1}{2}\zeta (\beta -1)-\zeta (\beta)\right) \right ]^{\frac{\beta -1}{\beta -2}}
\end{align*}
Thus we obtain an improved lower bound on the size of the set $R$ as follows:
\begin{align*}
|R| & \geq |E\setminus S|\\
%%    & \quad +(1-o(1))\underbrace{e^{\alpha}\frac{[(\beta -2)(\zeta (\beta -1)\slash 2-\zeta (\beta)+1 ]^{\frac{\beta -1}{\beta -2}}}{\beta -1}}_{=: t_{\beta}\cdot e^{\alpha}}
    & \quad +(1-o(1))e^{\alpha}\frac{[(\beta -2)(\zeta (\beta -1)\slash 2-\zeta (\beta)+1 ]^{\frac{\beta -1}{\beta -2}}}{\beta -1}
\end{align*}
We let $t_{\beta}:= e^{\alpha}\frac{[(\beta -2)(\zeta (\beta -1)\slash 2-\zeta (\beta)+1 ]^{\frac{\beta -1}{\beta -2}}}{\beta -1}$.
We obtain that the cost of the tour $\tau$ constructed by the M{\"o}mke-Svensson algorithm is bounded as
\begin{align*}
c(\tau ) & \leq \frac{4}{3}|E| - \frac{2}{3}|R|\\
         & \leq \frac{2}{3}|E|+\frac{2}{3}|S|-\frac{2}{3}t_{\beta}e^{\alpha}\\
         & \leq \left (\frac{2}{3}\zeta (\beta -1)+\frac{2}{3}\zeta (\beta)+\frac{5}{6}\right )e^{\alpha}
\end{align*}
Now we consider the general case when the subgraph induced by the vertices of degree at least $2$ is not $2$-vertex connected.
Let $G=(V,E)$ be the power law graph and $G'=(V',E')$ the subgraph induced by $\{v\in V|\text{deg}_G(v)\geq 2\}$. Suppose  that
$G'$ consists of $2$-vertex connected components $G'_1,\ldots , G'_L$, which are connected in a tree-like manner by bridges and/or articulation points.
Then we run the M{\"o}mke-Svensson algorithm separately on every component $G'_i=(V'_i,E_i),1\leq i\leq L$. Suppose that $\tau_1,\ldots , \tau_L$ are the tours constructed
in this way, and $(R_i,{\mathcal P}_i),i=1,\ldots , L$ are the associated removable pairs. Thus we have $c(\tau_i)\leq \frac{4}{3}|E_i|- \frac{2}{3}|R_i|$.
Now we observe that $\sum_i|R_i|\leq\sum_i|S_i|-\frac{2}{3}t_{\beta}e^{\alpha}$.
Combined with our lower bound for the cost of a tour, this yields the following result.
\begin{lemma}
For $2<\beta <2.48$, the approximation ratio of the M{\"o}mke-Svensson algorithm on power-law Graphic instances is at most
$\frac{\frac{2}{3}\zeta (\beta -1)+\frac{2}{3}\zeta (\beta)+\frac{5}{6}}{\frac{1}{2}+\max\{2,\zeta (\beta)+\frac{1}{2}\}}$.
\end{lemma}
Finally we give an estimate for the performance of Mucha's algorithm \cite{Mucha2012} on power law graphic instances. 
He shows that a tour can be constructed whose cost is at most $\frac{1}{3}n+\frac{10}{9}x(E)$. Here $x(E)$ denotes an optimum solution 
for the Held-Karp relaxation.
Using this upper bound and the lower bound $\max\{2,\zeta (\beta)+\frac{1}{2}\}$, we obtain an A.R. of
$\frac{10}{9}+\frac{\frac{1}{3}\zeta (\beta)}{\max\{2,\zeta (\beta)+\frac{1}{2}\}}$.
In Figure \ref{fig:PlotGraphTSP} we show the graphs of the approximation ratio for the MST heuristic, Christofides' algorithm, the M{\"o}mke-Svensson algorithm
and Mucha's algorithm for power law Graphic instances. 
%{\bf A.R. of various algorithms on Graphic PLG TSP.}
%\begin{itemize}
%\item MST Heuristic 
%\item Christofides' algorithm
%\item M{\"o}mke, Svensson
%\item Mucha 2012\\
%      He shows that a tour can be constructed whose cost is at most $\frac{1}{3}n+\frac{10}{9}x(E)$.
%      Using this upper bound and the lower bound $\max\{2,\zeta (\beta)+\frac{1}{2}\}$, we obtain an A.R. of 
%      $\frac{10}{9}+\frac{\frac{1}{3}\zeta (\beta)}{\max\{2,\zeta (\beta)+\frac{1}{2}\}}$.
%\end{itemize}
%%%%%%%%%%%%%%%%%%
%Let $G$ be a connected $(\alpha,\beta )$-power law graph and $c$ the associated shortest path metric on $V$. 
%Consider a tour $\tau=v_0\ldots v_{n-1}v_0$. We can write the cost of $\tau$ as
%\[c(\tau ) = \sum_{i=1}^n\frac{1}{2}(c(v_i,v_{(i-1)\mod n})+c(v_i,v_{i+1\mod n}))\]
%(half of the cost of all edges incident to $v_i$ in the tour $\tau$).

\begin{figure}[htb]
  \centering
  \input{PlotGraphTSP}
  \caption{Approximation ratios of the MST-algorithm (MST), \citeauthor{Christofides1976}' algorithm (Chr), \citeauthor{Mucha2012}'s algorithm (Mu) and the M\"{o}mke-Svensson algorithm (M-S) for Power Law Graphic TSP for $1<\beta<2.48$.}
  \label{fig:PlotGraphTSP}
\end{figure}
  

%\section{(1,2)-TSP with underlying Power Law Graph}
\section{(1,2)-TSP on Power Law Graphs}\label{sec:OneTwoTSP}

We consider now an interesting further special case of Metric TSP, namely the $(1,2)$-TSP where the distances between cities are either one or two. More precisely, we are given a complete undirected graph $G=(V,E)$ together with an edge weight function $w:E\to\{1,2\}$.
The problem is known to be NP-hard and MAX-SNP-complete as shown by \citeauthor{Papadimitriou1993} in \cite{Papadimitriou1993}. In the same paper they provided an approximation algorithm with approximation ratio $\frac{7}{6}$. After more than a decade this upper bound was slightly improved to $\frac{65}{56}$ by \citeauthor{Blaeser2005} in \cite{Blaeser2005}. The current best approximation algorithm is due to \citeauthor{Berman2006} and achieves an approximation ratio of $\frac{8}{7}$ as stated in \cite{Berman2006}.

Now we consider the special case of the $(1,2)$-TSP problem when the subgraph of $1$-edges is an $(\alpha,\beta )$-power law graph. In the following we refer to the subgraph of $1$-edges as the \emph{underlying} graph.

\subsection{Upper Bounds for Deterministic PLGs}\label{sec:DeterministicUpper}

Let $G=(V,E)$ be the underlying graph. This means that for $u\neq v$, the distance between $u$ and $v$ is $1$ iff $\{u,v\}\in E$, otherwise 
the distance is $2$. Now assume that $G$ is an $(\alpha,\beta )$-PLG for some $\beta >1$. 
In the following we make use of the methods and notations from \cite{Papadimitriou1993}. 

A \emph{cycle cover} $\mathcal{C}$ of a graph $G=(V,E)$ is a collection of vertex-disjoint cycles such that each vertex $v\in V$ is contained in a cycle of $\mathcal{C}$.
Suppose that there exists a cycle cover ${\mathcal C}$ (also called a 2-matching) of cost $n+k$, where $k$ is the number of $2$-edges, 
such that $\mathcal{C}$ does not contain any cycles of length less than four.  An optimum cycle cover with cycles of length at least four can be constructed
efficiently \cite{Hartvigsen1984,Manthey2008}.

Now let $v_1,v_2,\ldots , v_n,v_1$ be an optimum tour. Let $U$ be the set of nodes $v_i$ such that 
$d(v_i,v_{i+1})=2$. We may assume that ${\mathcal C}$ contains at most one cycle which also contains $2$-edges. 
All the other cycles of ${\mathcal C}$ are called pure.
Let $c_2$ be the number of pure cycles in ${\mathcal C}$ which contain at least one node from $U$.
In \cite{Papadimitriou1993}, two auxiliary graphs are constructed. 
First, the bipartite graph $B$ contains one node for each cycle from ${\mathcal C}$ and one node 
for each vertex from $V$. A cycle node - here just denoted as $C$, where $C\in {\mathcal C}$ - is connected to 
a node corresponding to vertex $v\in V$ if $v$ is not contained in $C$ but there exists an edge in $G$ connecting $v$ to a node in $C$.
Let $M$ be a maximum matching in $B$. The directed graph $F=({\mathcal C},A)$ contains an arc $(C,C')$ for every pair of cycles
$C,C'$ in ${\mathcal C}$ such that in $M$, $C$ is matched to a node in $C'$. Now $F$ contains a spanning subgraph $F'$ consisting of 
directed paths of length $2$, stars where there are directed edges from the leaves into the center node of the star and isolated nodes.
Let $r_2$ be the number of pure cycles (i.e. consisting only of $1$-edges) which are isolated in $F'$.
Let $n_2$ denote the total number of vertices which are contained in these cycles.
Since all the cycles in ${\mathcal C}$ are of length at least four, $r_2\leq n_2\slash 4$. Moreover, $r_2\leq c_2$.
In \cite{Papadimitriou1993}, a tour $\tau$ is constructed with 
\begin{equation}
\text{cost}(\tau)\leq n+k+\frac{2}{9}\left (n-n_2-k\right )+r_2
\end{equation}
Thus we obtain 
\begin{align*}
\text{cost}(\tau) & \leq  n+k+\frac{2}{9}\left (n-n_2-k\right )+\frac{n_2}{4}\\
                  & =     \frac{11}{9}n+\frac{7}{9}k+\frac{9-8}{36}n_2 = \frac{11}{9}n+\frac{7}{9}k+\frac{1}{36}c_2
\end{align*}
Let $\tau^*$ denote an optimum tour. Then
\begin{equation}
\text{cost}(\tau^*)\geq\max\{n+k,n+c_2\}
\end{equation}
We observe that for every $x\in [0,1]$, $\max\{n+k,n+c_2\}\geq (1-x)(n+k)+x(n+c_2)$. This yields the following bound on the approximation ratio
of this algorithm (for every $x\in [0,1]$):
\begin{align*}
\frac{\text{cost}(\tau )}{\text{cost}(\tau^*)} & \leq \frac{\frac{11}{9}n+\frac{7}{9}k+\frac{1}{36}c_2}{n+x(c_2-k)+k}
\end{align*}
Directly from the definition of $c_2$ we obtain that $c_2\leq k$.
%%
%%We consider the following two cases (directly from the definition of $c_2$ we obtain that $c_2\leq k$.\\[0.2ex]
%%{\sl Case 1: $c_2<k$.}\\[0.2ex]
Therefore we choose $x=0$ and obtain
\[\frac{\text{cost}(\tau )}{\text{cost}(\tau^*)}\leq\frac{\frac{11}{9}n+\left (\frac{7}{9}+\frac{1}{36} \right )k}{n+k}\]
The right hand side of this inequality is monotone decreasing in $k$.
Recall that $k$ is the number of $2$-edges in a minimum length cycle cover. 

For $\beta>1$ we have $n=\zeta (\beta )e^{\alpha}$. Moreover, the number of $2$-edges
in the optimum cycle cover is at least half the number of degree $1$ nodes in $G$. This yields
\begin{equation}
\frac{\text{cost}(\tau )}{\text{cost}(\tau^*)}\leq\frac{\frac{11}{9}\zeta (\beta )+\frac{29}{36}\cdot\frac{1}{2}}{\zeta (\beta )+\frac{1}{2}}
 = \frac{\frac{11}{9}\zeta (\beta )+\frac{29}{72}}{\zeta (\beta )+\frac{1}{2}}
\end{equation}
and thus the following theorem
\begin{theorem}\label{thm:DeterministicPLG}
 For $\beta>1$, there exists an approximation algorithm for $(1,2)$-TSP and underlying $(\alpha,\beta)$-PLG with approximation ratio $\frac{\frac{11}{9}\zeta (\beta )+\frac{29}{72}}{\zeta (\beta )+\frac{1}{2}}$.
\end{theorem}

In particular, for $(\alpha,\beta)$-PLGs with power law exponent $\beta>1.666$, the above theorem yields an improvement over current best general $(1,2)$-TSP bound of $\frac{8}{7}$ due to \cite{Berman2006} (see \autoref{fig:DetRatio}).

%\begin{figure}[ht]
% \input{DetRatio}
%\caption{}
%\label{fig:DetRatio}
%\end{figure}

%%{\sl Case 2: $c_2>k$.}\\[0.2ex]
%%In this case we choose $x=1$. We obtain 
%%\begin{equation}
%%\frac{\text{cost}(\tau )}{\text{cost}(\tau^*)}\leq\frac{\frac{11}{9}n+\frac{29}{36}c_2}{n+c_2}
%%\end{equation}
%%{\sl Case 3: $c_2=k$.}\\[0.2ex]
%%Let $G$ consist of connected components $G_1,\ldots , G_k$.
%%
%%We let $\tau$ denote a tour, and $\tau^*$ an optimum tour. Our first observation is that for each $1\leq i\leq k$, we may assume
%%$\tau\upharpoonright G_i$ and $\tau^*\upharpoonright G_i$ each to consist of a simple path:
%%\begin{lemma}{\bf (Path Reduction)}\\
%%Let $\tau$ be a tour such that for some $i$,
%%\end{lemma}

\subsection{The Case of Large Exponents}\label{sec:AsymptoticUpper}

Next we consider the asymptotic behaviour of the algorithm in \cite{Papadimitriou1993} for large power law exponents $\beta\to\infty$.
Recall that, for $\beta> 2$, $\zeta(\beta)\e^{\alpha}$ is the total number of nodes and $\e^{\alpha}$ is the number of degree $1$ nodes. Since $\zeta(\beta)\to 1$ as $\beta\to \infty$, at some point the number of degree $1$ nodes dominates the total number of nodes.
This enforces that some fraction of degree $1$ nodes must be adjacent to other degree $1$ nodes.
%In any tour $\tau$ these matching configurations are visited and left via $2$-edges, thus introducing a cost of $1.5$ per matched degree $1$ node to $\tau$.

Let $m_1$ be the number of degree $1$ nodes which are adjacent to another node of degree $1$.
We have that
\begin{align*}
 m_1 & \geq  \e^\alpha - \text{vol}([2,\Delta]) = \e^\alpha - \left(\zeta(\beta-1)\e^\alpha -\e^\alpha\right) = (2-\zeta(\beta-1))\e^\alpha %\sum_2^\Delta 
\end{align*}
The right hand side of this inequality is strictly positive for $\beta>2.729$. 
Since every degree $1$ node contributes an amount of $1.5$ to the cost of a tour and the contribution of every other node is at least one, the cost of any tour is at least $\e^\alpha\cdot 1.5 + (\zeta(\beta)-1)\e^\alpha$.
On the other hand, we can construct a tour containing $\frac{m_1}{2}$ edges connecting degree $1$ nodes by first contracting all these edges and then applying any TSP algorithm to the residual instance.
Since the contribution of every other node is at most $2$, we obtain an approximation ratio of
\begin{align*}
\frac{\frac{3}{2} m_1 + 2(\zeta(\beta)\e^\alpha - m_1)}{\frac{3}{2}\e^\alpha + (\zeta(\beta)-1)\e^\alpha} & = \frac{2\zeta(\beta)\e^\alpha - \frac{1}{2} m_1}{\frac{3}{2}\e^\alpha + (\zeta(\beta)-1)\e^\alpha}\\
 & \leq \frac{2\zeta(\beta)\e^\alpha - \frac{1}{2}(2-\zeta(\beta-1))\e^\alpha}{\frac{3}{2}\e^\alpha + (\zeta(\beta)-1)\e^\alpha}\\
  & = \frac{2\zeta(\beta) + \frac{1}{2}\zeta(\beta-1) -1}{\zeta(\beta)+ \frac{1}{2}}
\end{align*}
This yields the following theorem.
\begin{theorem}\label{thm:LargeExponents}
 For $\beta>2.729$, there exists an approximation algorithm for $(1,2)$-TSP and underlying $(\alpha,\beta)$-PLG with approximation ratio $\frac{2\zeta(\beta) + \frac{1}{2}\zeta(\beta-1) -1}{\zeta(\beta)+ \frac{1}{2}}$.
\end{theorem}

In \autoref{fig:DetRatio} we plot the approximation ratios for the deterministic case and the case of large exponents in comparison with the current best general upper bound of $\frac{8}{7}$ due to \cite{Berman2006}.
We observe that an improvement over $\frac{8}{7}$ is achieved for $\beta>3.765$ and an improvement over the bound $a(\beta)$ of \autoref{thm:DeterministicPLG} is achieved for $\beta>4.309$.

\begin{figure}[htb]
 \input{DetRatio}
\caption{Approximation ratios for the Power Law $(1,2)$-TSP as of \autoref{thm:DeterministicPLG}, $a(\beta)=\frac{\frac{11}{9}\zeta (\beta )+\frac{29}{72}}{\zeta (\beta )+\frac{1}{2}}$, and \autoref{thm:LargeExponents} ($\tilde{a}(\beta)=\frac{2\zeta(\beta) + \frac{1}{2}\zeta(\beta-1) -1}{\zeta(\beta)+ \frac{1}{2}}$) in comparison with the upper bound of $\frac{8}{7}$ due to \cite{Berman2006}.}
\label{fig:DetRatio}
\end{figure}


%\section{(1,2)-TSP with underlying Random PLG}
\subsection{Improved Upper Bounds for Random PLGs}\label{sec:RandomUpper}
Now we consider the case when the underlying graph $G$ is a random PLG. At first we present our general idea that will then yield improved approximation ratios for $(1,2)$-TSP with underlying random $(\alpha,\beta)$-PLG.

In the case of deterministic PLGs we have already made use of the following observation. The cost of a tour $\tau$ can be written as the sum of node costs $c_{\tau}(v)$, where
$c_{\tau}(v)$ is defined as $\frac{1}{2}$ times the cost of edges incident to $v$ in $\tau$. In the case of the $(1,2)$-TSP, $c_{\tau}(v)\geq 1$, since any of the two incident
edges has cost at least $1$. Moreover, if $v$ is a node of degree $1$, then $c_{\tau}(v)\geq \nicefrac{3}{2}$, since at least one of the two edges incident to $v$ has cost $2$.
This yields a lower bound  $k\geq\frac{\e^{\alpha}}{2}$ (see \autoref{sec:DeterministicUpper}). 
Now we want to improve this lower bound by taking into account the \emph{expected number} of low degree %degree $1$ and degree $2$ 
neighbors of nodes in an underlying random PLG. % $v$, $\deg{v}\geq 2(\zeta(\beta-1))$.
Let $\Gamma_i(v)$ be the set of degree $i$ neighbors of node $v$ and $N_i(v)=|\Gamma_i(v)|$ its cardinality.
Let $N_i(V)=\sum_{v\in V}N_i(v)$. 
Now we let $A_1(v)$ denote the additional lower bound of $k$ generated by degree $1$ neighbors of $v$, namely 
$A_1(v)=\min_{\tau}\sum_{u\in\Gamma_1(v)}(c_{\tau}(u)-\nicefrac{3}{2})$, where the minimum is over all tours $\tau$.
For a set $U\subseteq V$ of nodes we write  $A_1(U)=\sum_{v\in U}A_1(v)$. %Let $N_1(V)$ be the value added by degree $1$ neighbors of nodes in the underlying graph $G=(V,E)$.
Below we will show that $A_1(v)\geq\frac{N_1(v)}{2}-1$. We will also take into account the additional lower bound on the tour cost generated by degree $2$ neighbors of a node $v$.
This lower bound is inherently tour-dependent and will be denoted as $A_{2,\tau}(v)$, where $v$ is a node of degree $>2$ and $\tau$ is a tour.
It turns out that the values $A_{2,\tau}(v)$ are not independent from each other, and we will only be able to give a lower bound on the sum $A_{2,\tau}(V)$.

%Here  and $A_2(v)\geq\frac{N_2(v)}{2}-1$. %We show that $A_i(v)=\frac{N_i(v)}{2}-1$ for $i\in\{1,2\}$.
% The low degree neighbors connected by $1$-edges raise the lower bound on the value of $k$ in the following way: 
%Let $v$ be a node of degree $i$ with $j\leq i$ degree $1$ and degree $2$ neighbors, then this introduces an additional 
%value of at least $\frac{j}{2}-1$ to $k$. %(value $\frac{1}{2}$ for all but one) to $k$.
% This can be seen as follows. 
%%%%
%%%% gekommen bis hier MH Fr 04/09/15 14:59
%%%%

Let us first consider the case $i=1$. For the degree $1$ nodes we already accounted a value of $\frac{1}{2}$ for each node for our lower bound $k\geq\frac{\e^{\alpha}}{2}$. Now suppose that a node $v$ of degree $i$ has $j\leq i$ degree $1$ neighbors. This provides an additional value of $\frac{1}{2}$ for $j-2$ neighbors since any tour $\tau$ uses at most two $1$-edges connecting $v$. %the $j$ degree $1$ neighbors of $v$. %cycle cover!? 
The remaining $j-2$ neighbors are connected via $2$-edges.
In \autoref{fig:StarOne} we depict the situation around a node $v$ with $j$ degree $1$ neighbors. %We also show a possible tour around $v$ which enters and leaves $v$ via degree $1$ neighbors. 

\begin{figure}[htb]
 \centering
% \tikzsetnextfilename{StarOne}%
% \input{StarOne}
 \includegraphics[scale=1]{StarOne}
 \caption{(left) Node $v$ with $j$ degree $1$ neighbors. (right) A possible tour around $v$ which enters and leaves $v$ via degree $1$ neighbors and matches the remaining degree $1$ vertices via $2$-edges. Since we already accounted $\frac{1}{2}$ for every degree $1$ vertex, this introduces an additional value of $A_1(v)=\frac{j}{2}-1$.}
 \label{fig:StarOne}
\end{figure}

Now we turn to the case $i=2$. We will first give a definition of the terms $A_{2,\tau}(v)$. Then we will prove that for every tour $\tau$ the two inequalities
$c(\tau)\geq n+e^{\alpha}\slash 2+A_1(V)+A_{2,\tau}(V)$ and $A_{2,\tau}(V)\geq\sum_{\text{deg}(v)>2}\frac{1}{2}\cdot (N_2(v)-2)$ hold.
Recall that for a tour $\tau$ and a node $v\in V$, the tour cost of $v$, $c_{\tau}(v)$ is defined as the sum of half of all the edge costs of tour edges incident to $v$. 
The set of neighbors of $v$ in $G$ is denoted as $\Gamma_G(v)$. Moreover, we let $\Gamma_{\tau}(v)$ denote the set of nodes which are adjacent to $v$ in the tour $\tau$.
$\Gamma_{2,\tau}(v)$ denotes the set of nodes of degree $2$ in $G$ which are adjacent to $v$ in $\tau$. For nodes $v\in V$ of degree $\text{deg}(v)>2$ we let
\[A_{2,\tau}(v)\: =\: \sum_{u\in \Gamma_G(v)\setminus\Gamma_{2,\tau}(v)}\frac{c_{\tau}(u)-1}{|\{v'|\text{deg}(v')>2,\: v'\in \Gamma_G(u)\setminus\Gamma_{\tau}(u)\}|},\]
and $A_{2,\tau}(v)=0$ otherwise.
The following lemma shows that using the values $A_1(v),A_{2,\tau}(v)$, we obtain a lower bound for the cost of a given tour $\tau$.
\begin{lemma}
For every tour $\tau$, $c(\tau)\geq n+\frac{e^{\alpha}}{2}+A_1(V)+A_{2,\tau}(v)$.
\end{lemma}
\begin{proof}
We let $A_{1,\tau}(v)=\sum_{u\in\Gamma_1(v)}(c_{\tau}(u)-\nicefrac{3}{2})$. We observe that for every node $v$ in $G$, $c_{\tau}(v)\geq 1$, and for every node $u$ of degree $1$,
$c_{\tau}(u)\geq\nicefrac{3}{2}$. We obtain
\begin{align*}
c(\tau ) & = \sum_{v}c_{\tau}(v)\\
         & \geq n +\frac{e^{\alpha}}{2}+\sum_{\text{deg}(u)=1}(c_{\tau}(u)-\nicefrac{3}{2}) + \sum_{\text{deg}(u)=2}(c_{\tau}(u)-1)\\
         & \geq n +\frac{e^{\alpha}}{2}+\sum_{\text{deg}(v)>2}\sum_{u\in\Gamma_1(v)}(c_{\tau}(u)-\nicefrac{3}{2}) + \sum_{\text{deg}(u)=2}(c_{\tau}(u)-1)
\end{align*}
We observe that for every node $u$ of degree $2$, 
\[c_{\tau}(u)-1=\sum_{v\in\Gamma_G(u)\setminus\Gamma_{\tau}(u),\text{deg}(v)>2}\frac{c_{\tau}(u)-1}{|\{v'|\text{deg}(v')>2,\: v'\in \Gamma_G(u)\setminus\Gamma_{\tau}(u)\}|}\]
This concludes the proof of the lemma.
\end{proof} 
%%For the case $i=2$ 
Now assume that a node $v$ of degree $>2$ has $l$ degree $2$ neighbors. Again, any tour $\tau$ uses at most two $1$-edges while visiting $v$. 
The remaining $l-2$ neighbors may be entered via $1$-edges but then only left via $2$-edges for which we may account an additional value of $\frac{1}{2}$. 
In \autoref{fig:StarTwo} we depicted the situation around a node $v$ with $l$ neighbors of degree $2$.

\begin{figure}[htb]
 \centering
% \tikzsetnextfilename{StarTwo}%
% \input{StarTwo}
 \includegraphics[scale=1]{StarTwo}
 \caption{(left) Node $v$ with $l$ degree $2$ neighbors. (right) A possible tour around $v$ which enters and leaves $v$ via degree $2$ neighbors and matches the remaining degree $2$ vertices pairwise via $2$-edges. This introduces an additional value of $A_2(v)=\frac{l}{2}-1$.}
 \label{fig:StarTwo}
\end{figure}
We will now prove the following lower bound on the contribution of degree $2$ neighbors to the cost of a tour.
\begin{lemma}
For every tour $\tau$, $A_{2,\tau}(V)=\sum_{v,\text{deg}(v)>2}A_{2,\tau}(v)\geq\sum_{\text{deg}(v)>2}\frac{1}{2}\cdot (N_2(v)-2)$.
\end{lemma}
\begin{proof}
Consider a pair of nodes $v,u$ with $\text{deg}(v)>\text{deg}(u)=2$ such that $u$ and $v$ are adjacent in $G$ but not in $\tau$.
Let $v'$ be the other neighbor of $u$. Since $v$ is not adjacent to $u$ in the tour $\tau$, the node $u$ is incident to at least one tour edge of cost $2$.
Now we consider three different cases concerning the other neighbor $v'$.
If $v'$ is a node of degree $\leq 2$, then we do not have to charge anything to $v'$, and thus we can charge $c_{\tau}(u)-1\geq \nicefrac{3}{2}-1=\nicefrac{1}{2}$ to $v$.
If $v'$ is a node of degree $>2$ which is adjacent to $u$ within the tour $\tau$, we can also charge $c_{\tau}(u)-1\geq \nicefrac{1}{2}$ to $v$.
In the remaining case, $v'$ is a node of degree $>2$ which is not adjacent to $u$ in $\tau$. But then $u$ is incident to two edges of cost $2$ in $\tau$, which implies
$c_{\tau}(u)-1=2-1=1$, and we can charge $\nicefrac{1}{2}$ to $v$ and $\nicefrac{1}{2}$ to $v'$. The same holds when $v=v'$ and $u$ is not adjacent to $v$ in $\tau$. 
Finally we observe that for every node $v$ of degree $>2$, all but at most two degree $2$ neighbors of $v$ are not adjacent to $v$ in $\tau$. This concludes the 
proof of the lemma.
%%It is sufficient to prove that for every node $u$ of degree $2$
\end{proof}
In the following we quantify the effect of the above considerations and the resulting upper approximation bounds for the case of $(1,2)$-TSP and underlying random $(\alpha,\beta)$-PLGs. We present separate analyses for the three subcases $\beta>2$, $\beta=2$ and $1<\beta<2$.

\paragraph{Resulting Upper Bounds for $\beta>2$}

We are going to estimate the value $A_1(V)$ for the case that the underlying graph is an $(\alpha,\beta)$ power law graph $\gab=(V,E)$ and for power law exponents $\beta>2$. We show the following lemma.
\begin{lemma}\label{lem:Ek_One}
 Let $\beta> 2$ and $\gab=(V,E)\in\Gab$ be a random PLG in the $\Mab$ model. %due to \cite{Aiello2001}. 
 We have that %For the random PLG model, we have that
 \[\E[A_1(V)] \geq \frac{\e^{\alpha}}{\zeta(\beta-1)^{\beta-1}2^{\beta-1}}\left(\frac{1}{(\beta-2)(\beta-1)}-\frac{1}{4\zeta(\beta-1)}\right).\]
\end{lemma}
\begin{proof}

%In order to improve the lower bound on $k$
First we give a lower bound for the expected number of degree $1$ neighbors of a node $v$ of degree $i$.
\begin{align*}
 \E[N_1(v)] &= \sum_{j=1}^{i}\Pr(\text{$j$-th neighbor has deg. $1$})\\
  &= \sum_{j=1}^{\e^{\alpha}}\Pr(\text{the $j$-th deg. $1$ node will be adjacent to $v$})\\
  &= \e^{\alpha}\frac{i}{\zeta(\beta-1)\e^{\alpha}-1} = \frac{i}{\zeta(\beta-1)-\e^{-\alpha}} \geq \frac{i}{\zeta(\beta-1)}
\end{align*}
Thus, the expected additional value for a node $v$ of degree $i$ contributing to $k$ is $\E[A_1(v)]=\frac{i}{2\zeta(\beta-1)}-1$. This value is positive for $i\geq 2\zeta(\beta-1)$.
Summing up over all vertices with sufficiently large degrees, we obtain %for the expected number of $2$-edges:
\begin{align}
 \E[A_1(V)] &\geq \sum_{i=2\zeta(\beta-1)}^{\Delta}\frac{\e^{\alpha}}{i^{\beta}}\left(\frac{i}{2\zeta(\beta-1)}-1\right)\label{eq:EA_11}
\end{align}
Replacing the sums in (\ref{eq:EA_11}) by the corresponding integral, we get the following lower bound on $\E[A_2(V)]$:
\begin{align*}
 \E[A_1(V)] &\geq \frac{\e^{\alpha}}{2\zeta(\beta-1)}\left(\int_{2\zeta(\beta-1)}^{\Delta}\frac{1}{x^{\beta-1}} dx + \frac{1}{2}\left(\frac{1}{(2\zeta(\beta-1))^{\beta-1}}-\frac{1}{\Delta^{\beta-1}}\right)\right)\\
  &\quad - \e^{\alpha}\left(\int_{2\zeta(\beta-1)}^{\Delta}\frac{1}{x^{\beta}}+\frac{1}{(2\zeta(\beta-1))^{\beta}}-\frac{1}{\Delta^{\beta}}\right) + \frac{\e^{\alpha}}{\Delta^{\beta}\left(\frac{\Delta}{2\zeta(\beta-1)}-1\right)}
   \end{align*}
The anti-derivative now has the following form
   \begin{align*}
  &\E[A_1(V)] \geq \frac{\e^{\alpha}}{2\zeta(\beta-1)}\left(\left[\frac{x^{2-\beta}}{2-\beta}\right]_{2\zeta(\beta-1)}^{\Delta}+\frac{1}{2}\left(\frac{1}{(2\zeta(\beta-1))^{\beta-1}}-\frac{1}{\Delta^{\beta-1}}\right)\right)\\
  &\qquad -  \e^{\alpha}\left(\left[\frac{x^{1-\beta}}{1-\beta}\right]_{2\zeta(\beta-1)}^{\Delta}+\frac{1}{(2\zeta(\beta-1))^{\beta}}-\frac{1}{\Delta^{\beta}}\right) + \frac{\Delta}{2\zeta(\beta-1)}-1\\
  &= \frac{\e^{\alpha}}{2\zeta(\beta-1)}\left(\frac{1}{(\beta-2)(2\zeta(\beta-1))^{\beta-2}}-\frac{1}{(\beta-2)\Delta^{\beta-2}}+\frac{1}{2^{\beta}\zeta(\beta-1)^{\beta-1}}-\frac{1}{2\Delta^{\beta-1}}\right)\\
  &\qquad - \e^{\alpha}\left(\frac{1}{(\beta-1)(2\zeta(\beta-1))^{\beta-1}}-\frac{1}{(\beta-1)\Delta^{\beta-1}}+\frac{1}{2^{\beta}\zeta(\beta-1)^{\beta}}-\frac{1}{\Delta^{\beta}}\right) + o(\e^{\alpha})\\
%%  &= \frac{\e^{\alpha}}{2}+\e^{\alpha}\left(\frac{1}{(\beta-2)2^{\beta-1}\zeta(\beta-1)^{\beta-1}}+\frac{1}{2^{\beta+1}\zeta(\beta-1)^{\beta}}\right.\\ 
%%  &\qquad \left.-\frac{1}{(\beta-1)2^{\beta-1}\zeta(\beta-1)^{\beta-1}}-\frac{1}{2^{\beta}\zeta(\beta-1)^{\beta}}- o(1)\right)\\
  &= \frac{\e^{\alpha}}{\zeta(\beta-1)^{\beta-1}2^{\beta-1}}\left(\frac{1}{\beta-2}+\frac{1}{4\zeta(\beta-1)}-\frac{1}{\beta-1}-\frac{1}{2\zeta(\beta-1)} - o(1)\right)\\
  &= \frac{\e^{\alpha}}{\zeta(\beta-1)^{\beta-1}2^{\beta-1}}\left(\frac{1}{(\beta-2)(\beta-1)}-\frac{1}{4\zeta(\beta-1)}\right)
\end{align*}
This concludes the proof of the lemma.
\end{proof}

Next, we want to further improve the expected lower bound on $k$ similar to \autoref{lem:Ek_One} by taking into account the additional value generated by degree $2$ neighbors of nodes in the underlying graph $\gab$.

%Again, suppose that a node $v$ of degree $i$ has $j\leq i$ degree $2$ neighbors, then this provides an additional value of $\frac{1}{2}$ for $j-2$ neighbors.
Let $A_2(V)$ be the value added by degree $2$ neighbors of nodes in the underlying graph $G=(V,E)$. We prove the following lemma.
\begin{lemma}\label{lem:Ek_Two}
 Let $\gab=(V,E)\in\Gab$ be a random PLG in the $\Mab$ model. % due to \cite{Aiello2001}. 
 We have that %For the random PLG model, we have that
 \[\E[A_2(V)]\geq (1-o(1))\e^{\alpha}\left(\frac{2^{-\beta(\beta-1)}\zeta(\beta-1)^{1-\beta}}{(\beta-1)(\beta-2)}+\frac{1}{\zeta(\beta-1)^{\beta}}\left(\frac{1}{2^{\beta\cdot\beta+1}}-\frac{1}{2^{2\beta}}\right)\right).\]
\end{lemma}
\begin{proof}
 First we give a lower bound for the expected number of degree $2$ neighbors of a node $v$ of degree $i$. 
 %Let $N(2,i)$ be the number of degree $2$ neighbors of some vertex $v$ of degree $i$. We want to compute the value $\E(N(2,i))$. %In order to achieve this
 \begin{align*}
  \E[N_2(v)] &= \sum_{j=1}^{i}\Pr(\text{$j$-th neighbor has deg. $2$})\\
  &= \sum_{j=1}^{\frac{\e^{\alpha}}{2^{\beta}}}\Pr(\text{the $j$-th deg. $2$ node will be adjacent to $v$})\\
  &= \frac{\e^{\alpha}}{2^{\beta}}\left(\frac{i}{\zeta(\beta-1)\e^{\alpha}-1} + \frac{\zeta(\beta-1)\e^{\alpha}-1-i}{\zeta(\beta-1)\e^{\alpha}-1} \cdot \frac{i}{\zeta(\beta-1)\e^{\alpha}-2}\right)\\
  &> \frac{\e^{\alpha}}{2^{\beta}} \cdot \frac{2i}{\zeta(\beta-1)\e^{\alpha}} = \frac{i}{2^{\beta-1}\zeta(\beta-1)}
 \end{align*}
 Now, the expected additional value for a node $v$ of degree $i$ contributing to $k$ is $\E[A_2(v)]=\frac{i}{2^{\beta}\zeta(\beta-1)}-1$. This value is positive for $i\geq 2^{\beta}\zeta(\beta-1)$.
Summing up over all vertices with sufficiently large degrees, we obtain 
\begin{align}
  \E[A_2(V)] &\geq \sum_{i=2^{\beta}\zeta(\beta-1)}^{\Delta} \frac{\e^{\alpha}}{i^{\beta}}\left(\frac{i}{2^{\beta}\zeta(\beta-1)}-1\right)\nonumber\\
   &= \frac{\e^{\alpha}}{2^{\beta}\zeta(\beta-1)} \sum_{i=2^{\beta}\zeta(\beta-1)}^{\Delta} \frac{1}{i^{\beta-1}}-\e^{\alpha} \sum_{i=2^{\beta}\zeta(\beta-1)}^{\Delta} \frac{1}{i^{\beta}}.\label{eq:EA_21}
\end{align} %for the expected number of $2$-edges:
Replacing the sums in (\ref{eq:EA_21}) by the corresponding integral, we obtain the inequality
 \begin{align*}
  \E[A_2(V)] &\geq \frac{\e^{\alpha}}{2^{\beta}\zeta(\beta-1)} \left(\frac{1}{\Delta^{\beta-1}}+\int_{2^{\beta}\zeta(\beta-1)}^{\Delta}x^{1-\beta}dx+\frac{1}{2}\left(\frac{1}{(2^{\beta}\zeta(\beta-1))^{\beta-1}}-\frac{1}{\Delta^{\beta-1}}\right)\right) \\
   &\qquad - \e^{\alpha} \left(\frac{1}{\Delta^{\beta}}+\int_{2^{\beta}\zeta(\beta-1)}^{\Delta}x^{-\beta}dx+\frac{1}{(2^{\beta}\zeta(\beta-1))^{\beta}}-\frac{1}{\Delta^{\beta}}\right)
   \end{align*}
The anti-derivative now has the following form
   \begin{align*}
 \E[A_2(&V)] \geq \frac{\e^{\alpha}}{2^{\beta}\zeta(\beta-1)} \left(\left[\frac{x^{2-\beta}}{2-\beta}\right]_{2^{\beta}\zeta(\beta-1)}^{\Delta}+\frac{1}{2^{\beta(\beta-1)+1}\zeta(\beta-1)^{\beta-1}}+\frac{1}{2\Delta^{\beta-1}}\right)\\
   &\qquad -\e^{\alpha} \left(\left[\frac{x^{1-\beta}}{1-\beta}\right]_{2^{\beta}\zeta(\beta-1)}^{\Delta}+\frac{1}{2^{2\beta}\zeta(\beta-1)^{\beta}}\right)\\
   &= \frac{\e^{\alpha}}{2^{\beta}\zeta(\beta-1)} \left(\frac{(2^{\beta}\zeta(\beta-1))^{2-\beta}-\Delta^{2-\beta}}{\beta-2}+\frac{1}{2^{\beta(\beta-1)+1}\zeta(\beta-1)^{\beta-1}}+\frac{1}{2\Delta^{\beta-1}}\right)\\
   &\qquad -\e^{\alpha} \left(\frac{(2^{\beta}\zeta(\beta-1))^{1-\beta}-\Delta^{1-\beta}}{\beta-1}+\frac{1}{2^{2\beta}\zeta(\beta-1)^{\beta}}\right)\\
   &= \e^{\alpha} \left(\frac{1}{(\beta-2)2^{\beta(\beta-1)}\zeta(\beta-1)}+\frac{1}{2^{\beta\cdot\beta+1}\zeta(\beta-1)^{\beta}}-\frac{1}{(\beta-1)2^{\beta(\beta-1)}\zeta(\beta-1)}\right. \\
   &\qquad \left.-\frac{1}{2^{2\beta}\zeta(\beta-1)^{\beta}} - o(1)\right)\\
   &= (1- o(1))\e^{\alpha} \left(\frac{2^{-\beta(\beta-1)}\zeta(\beta-1)^{1-\beta}}{(\beta-1)(\beta-2)}+\frac{1}{\zeta(\beta-1)^{\beta}}\left(\frac{1}{2^{\beta\cdot\beta+1}}-\frac{1}{2^{2\beta}}\right)\right)
 \end{align*}
 This concludes the proof of the lemma.
\end{proof}

From \autoref{lem:Ek_One} and \autoref{lem:Ek_Two} we obtain the following corollary.
\begin{corollary}
Let $k$ be the number of $2$-edges in the optimum cycle cover of a $(1,2)$-TSP instance with underlying power law graph $\gab\in\Gab$ drawn from $P(\alpha,\beta )$. We have
 \begin{align*}
  \E[k] &\geq \frac{\e^{\alpha}}{2} + \E[A_1(V)] + \E[A_2(V)]\\
  &\geq \frac{\e^{\alpha}}{2} + \frac{\e^{\alpha}}{\zeta(\beta-1)^{\beta-1}2^{\beta-1}}\left(\frac{1}{(\beta-2)(\beta-1)}-\frac{1}{4\zeta(\beta-1)}\right)\\
  &\qquad + \e^{\alpha}\left(\frac{2^{-\beta(\beta-1)}\zeta(\beta-1)^{1-\beta}}{(\beta-1)(\beta-2)}+\frac{1}{\zeta(\beta-1)^{\beta}}\left(\frac{1}{2^{\beta\cdot\beta+1}}-\frac{1}{2^{2\beta}}\right)\right) =: E_k
 \end{align*}
\end{corollary}

From the above corollary we finally obtain
\begin{theorem}\label{thm:Beta>2}
  For $\beta>2$, there exists an approximation algorithm for $(1,2)$-TSP and underlying \emph{random} $(\alpha,\beta)$-PLG with expected 
approximation ratio $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot E_k}{\zeta(\beta)+E_k}$.
\end{theorem}

In \autoref{fig:RandomRatio1} we compare the expected approximation ratio $\hat{a}(\beta)$ of \autoref{thm:Beta>2} to the ratio $a(\beta)$ achieved in the deterministic setting (\autoref{thm:DeterministicPLG}).

\begin{figure}[htb]
  \input{RandomRatio}
  \caption{Plot of the expected approximation ratio $\hat{a}(\beta)$ of \autoref{thm:Beta>2} as compared to the ratio $a(\beta)$ achieved in the deterministic setting (\autoref{thm:DeterministicPLG}).}
  \label{fig:RandomRatio}
\end{figure}

\paragraph{Resulting Upper Bound for $\mathbf{1<\beta<2}$}

We consider now the case when the power law exponent $\beta$ satisfies $1<\beta<2$.
Again we will give estimates for the expected additional contribution of degree $1$ and degree $2$ nodes $A_1(V)$ and $A_2(V)$. 
%%Similar to the above paragraph we are going to estimate the values $A_1(V)$ and $A_2(V)$ now for the case of power law exponents $1<\beta<2$. 
The contribution of degree $1$ nodes is given in the following lemma.
\begin{lemma}\label{lem:Ek_One2}
 Let $1<\beta<2$ and $\gab=(V,E)\in\Gab$ be a random PLG in the $\Mab$ model. % due to \cite{Aiello2001}. 
 We have that %For the random PLG model, we have that
 $\E[A_1(V)] \geq \e^{\alpha}$.
\end{lemma}
The proof is similar to that of \autoref{lem:Ek_One}.
The expected number of degree $1$ neighbors of a node $v$ can be lower bounded by $\e^\alpha\frac{\text{deg}(v)}{2|E|-1}\geq(2-\beta)\text{deg}(v)\e^{\alpha(1-\nicefrac{2}{\beta})}$.
Based on this we obtain
\[\E[A_1(V)]\geq \frac{\e^\alpha}{2}+\sum_{\frac{4}{2-\beta}\e^{\alpha(\nicefrac{2}{\beta}-1)}}^\Delta \frac{2-\beta}{2} j^{1-\beta} \e^{\alpha(2-\nicefrac{2}{\beta})}.\]
We estimate the sums by integrals and finally obtain $\E[A_1(V)]\geq\e^\alpha$.

The case of degree $2$ nodes being adjacent to nodes of higher degree is considered in the following lemma.
\begin{lemma}\label{lem:Ek_Two2}
 Let $1<\beta<2$ and $\gab=(V,E)\in\Gab$ be a random PLG in the $\Mab$ model. % due to \cite{Aiello2001}. 
 We have that %For the random PLG model, we have that
 $\E[A_2(V)] \geq \frac{1}{4}\e^{\alpha}$.
\end{lemma}
\begin{proof}
 We start by estimating the expected number of degree $2$ neighbors of high degree nodes in $\gab$. Suppose $v$ is a node of degree $i$.
 Then we have
%% First, we calculate the expected number of degree $2$ neighbors of a node $v$ of degree $i$.
 \begin{align*}
  \E[N_2(v)] 
  %&= \sum_{j=1}^{i}\Pr(\text{$j$-th neighbor has deg. $2$})\\
  %&= \sum_{j=1}^{\frac{\e^{\alpha}}{2^{\beta}}}\Pr(\text{the $j$-th deg. $2$ node will be adjacent to $v$})\\
  &= \frac{\e^{\alpha}}{2^{\beta}}\left(\frac{i}{\frac{\e^{2\alpha/\beta}}{2-\beta}-1} + \frac{\frac{\e^{2\alpha/\beta}}{2-\beta}-1-i}{\frac{\e^{2\alpha/\beta}}{2-\beta}-1} \cdot \frac{i}{\frac{\e^{2\alpha/\beta}}{2-\beta}-2}\right)\\
  &> \frac{(2-\beta)\e^{\alpha}}{2^{\beta}} \cdot \frac{i}{\e^{2\alpha/\beta}} = \frac{2-\beta}{2}\cdot\frac{i}{\e^{\alpha(\frac{2}{\beta}-1)}}
 \end{align*}
 Therefore, the expected additional contribution to $k$ generated by a node $v$ of degree $i$ in $\gab$ is
%% Now, the expected additional value for a node $v$ of degree $i$ contributing to $k$ is 
$\E[A_2(v)]=\frac{2-\beta}{4}\cdot\frac{i}{\e^{\alpha(2/\beta-1)}}-1$. This value is positive for $i\geq \e^{\alpha(2/\beta-1)}\cdot \frac{4}{2-\beta}=:\delta$. 
Summing up over all nodes with sufficiently large degrees we obtain %such that the expected value is at least $2$.
 \begin{align*}
  \E[A_2(V)] &= \sum^\Delta_\delta \frac{\e^\alpha}{i^\beta}\left(\frac{2-\beta}{4}\cdot\frac{i}{\e^{\alpha(2/\beta-1)}}-1\right)\\
  &\geq \sum^\Delta_\delta \left(\frac{2-\beta}{4}\cdot\frac{i^{1-\beta}}{\e^{2\alpha(1/\beta-1)}}-\frac{\e^\alpha}{i^\beta}\right)\intertext{We replace the sum 
by the corresponding integral, we obtain}
  \E[A_2(V)] &\geq \int^{\Delta+1}_\delta x^{1-\beta}dx\cdot \frac{2-\beta}{4}\e^{2\alpha(1-1/\beta)} + \frac{2-\beta}{8}\e^{2\alpha(1-1/\beta)}\left(\left(\frac{4}{2-\beta}\e^{\alpha(2/\beta-1)}\right)^{1-\beta}\right.\\
  &\quad -(\Delta+1)^{1-\beta}\Bigg)
   -\e^{\alpha}\left(\int^{\Delta+1}_\delta x^{-\beta}dx + \left(\frac{4}{2-\beta}\e^{\alpha(2/\beta-1)}\right)^{-\beta}-(\Delta+1)^{-\beta}\right)
 \end{align*}
Again we make use of anti-derivatives in order to estimate the integral terms.
Then by rearranging terms we obtain $\E[A_2(V)] \geq \nicefrac{1}{4}\e^\alpha$.
This concludes the proof of the lemma.
 \end{proof}
 
From the above \autoref{lem:Ek_One2} and \autoref{lem:Ek_Two2} we obtain the following result.
\begin{theorem}\label{thm:1Beta2}
  For $1<\beta<2$, there exists an approximation algorithm for $(1,2)$-TSP and underlying \emph{random} $(\alpha,\beta)$-PLG with 
approximation ratio $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot\frac{5}{4}}{\zeta(\beta)+\frac{5}{4}}$.
\end{theorem}

\paragraph{Resulting Upper Bound for $\mathbf{\beta=2}$}

In the case when the power law exponent is $\beta=2$, we proceed similarly and obtain the following result.

\begin{theorem}\label{thm:Beta=2}
  For $\beta=2$, there exists an approximation algorithm for $(1,2)$-TSP and underlying \emph{random} $(\alpha,\beta)$-PLG with 
approximation ratio $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot\frac{5}{8}}{\zeta(\beta)+\frac{5}{8}}$.
\end{theorem}

\autoref{fig:RandomRatio1} shows the approximation ratio for $(1,2)$-TSP on random $(\alpha,\beta)$-PLGs for the three subcases $1<\beta<2$, $\beta=2$ and $\beta>2$.
  
\begin{figure}[htb]
  \input{RandomRatio1}
  \caption{Expected Approximation ratio for Random Power Law $(1,2)$-TSP for $1<\beta<2$ ($\tilde{a}(\beta)$, \autoref{thm:1Beta2}), $\beta=2$ (${a}(\beta)$, \autoref{thm:Beta=2}) and $\beta>2$ ($\hat{a}(\beta)$, \autoref{thm:Beta>2}).}
  \label{fig:RandomRatio1}
\end{figure}

DetRatio.tex
\begin{asy}
 defaultpen(fontsize(11));
 import graph;
 import gsl;
     size(15cm,10cm,IgnoreAspect);
     

     pen dashed=linetype(new real[] {4,4});
     pen p=linewidth(.75);

     real g(real x) {return 8/7;}
     //real f(real x) {return 13/12;}
     real e(real x) {return (2*zeta(x) + 0.5*zeta(x-1) -1)/(zeta(x) + 0.5);}
     pair E(real x) {return (x,e(x));}
     real h(real x) {return ((11/9*zeta(x)+29/72)/(zeta(x)+1/2));}
     pair H(real x) {return (x,h(x));}
  
     draw("",graph(g,1.1,9),dotted+p,"first analysis ($\rho$)");
     //draw("",graph(f,1.1,9),dotted+p,"second analysis ($\rho'$)");
     draw("",graph(e,2.729,4.309),dashed+p,"second analysis ($\rho'$)");
     draw("",graph(h,1.1,4.309),p,"second analysis ($\rho'$)");
     draw("",graph(e,4.309,9),p,"second analysis ($\rho'$)");
     draw("",graph(h,4.309,9),dashed+p,"second analysis ($\rho'$)");
     
     ylimits(1,e(2.729));
     //ytick("$\frac{8}{7}$",(1,8/7));
     //ytick("$\frac{13}{12}$",(1,13/12));
     //ytick("$1$",(1,1));
     //labely(1,E);
     label("$\frac{8}{7}$",(9,8/7),E);
     //label("$\frac{13}{12}$",(9,13/12),E);
     label("$a(\beta)=\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{72}}{\zeta(\beta)+\frac{1}{2}}$",H(6),NE);
     label("$\tilde{a}(\beta)=\frac{2\cdot\zeta(\beta) + \frac{1}{2}\zeta(\beta-1) -1}{\zeta(\beta)+ \frac{1}{2}}$",E(3.3),NE);
     xaxis("$\beta$",BottomTop,LeftTicks);
     yaxis("approx. ratio",LeftRight,RightTicks);

     //attach(legend(),(point(S).x,truepoint(S).y),10S,UnFill);
  \end{asy}
Intro.tex
\section{Introduction}

%Power law graphs (PLG) are used in the analysis of real-world networks 
%Many of the existing real-world networks turn out to 
%It has 
Given a set of cities along with the distance between each pair of them, the \emph{Traveling Salesman Problem} (TSP) is to find the shortest tour through all the cities and returning to the starting point.
The TSP is one of the best known problems in combinatorial optimization and has many applications, for example in the fields of logistics, genetics and telecommunications.
It is well known that the general TSP is $NP$-hard \cite{Karp1972} and that, unless $P=NP$, there can be no efficient approximation algorithm for the TSP that achieves some bounded approximation ratio \cite{Sahni1976}.
For the case of the (symmetric) \emph{Metric TSP} with a distance function satisfying the triangle inequality Christofides devised a $\nicefrac{3}{2}$-approximation algorithm \cite{Christofides1976} which has seen no improvement for nearly four decades.
But a number of improvements were made for some special cases of Metric TSP (see e.g. \cite{Berman2006,Sebo2014}). % \cites(a)(b)[c][d]{AT2015}
We refer to %\defcitealias{AT2015}{AT15}\entryneedsurl{AT2015}\cite{AT2015}
\entryneedsurl{Taxonomy2015}\cite{Taxonomy2015} and \cite{Karpinski2015} for an overview of some of the current approximability and inapproximability results.
%We refer to the survey articles by \citeauthor{Vygen2012} and \citeauthor{Lampis2014} for an overview of some of the current approximability and inapproximability results \entryneedsurl{Vygen2012}\cite{Vygen2012,Lampis2014}.

In this paper we study two special cases of Metric TSP, namely, the \emph{$(1,2)$-TSP} with %symmetric distance function and 
distances between cities being either one or two, and the \emph{Graphic TSP} where we assume that the metric is the shortest path metric of an undirected graph.
More precisely we are interested in the case of Graphic TSP where the underlying graph is a \emph{power law graph}, and, for the $(1,2)$-TSP, where the undirected graph of $1$-edges is a power law graph.

Power law graphs have the property that their node degree distribution follows a power law, 
i.e. the number of nodes of degree $i$ is proportional to $i^{-\beta}$, for some fixed power law exponent $\beta >0$.
This parameter $\beta$ is called the power law exponent.
Many of the existing real-world networks turn out to be power law graphs. This has been observed for the graphs of the Internet and the World Wide Web (WWW), 
peer-to-peer networks, gene regulatory networks and protein interaction networks and for social networks.

% Ferrante et al. \cite{Ferrante2008} showed the NP-hardness of Max Clique in power law graphs for $\beta\geq 1$ and of MIS in power law graphs for all $\beta >0$. 
% Shen et al. \cite{Shen2012} proved the APX-hardness of Max Clique and Maximum Independent Set on power law graphs, also for $\beta >1$. 
% Their result is based on an efficient embedding of bounded degree graphs into power law graphs. 




% \section{Introduction}
% 
% In recent years topological analyses have been applied to a variety of real world graphs such as the World-Wide Web, the Internet, Collaboration and Social Networks, Protein Interaction Networks and other large-scale graphs of biological systems.
% Typical statistical parameters such as the \emph{diameter}, \emph{robustness}, \emph{clustering coefficient} and \emph{degree distribution} have been measured and compared to the expected values of these parameters in \emph{uniform} random graph models such as the classical $G(n,p)$ model due to Erd\H{o}s and Rényi \cite{Erdos1960}. It turned out that the real world graphs are significantly different from the uniform random models with respect to these statistical and topological properties. In subsequent studies the aim was to describe the properties of real world networks mathematically and to propose new models in order to meet these conditions.
% 
% As of 1999 Kumar et. al. \cite{Broder2000,Kumar2000}, Kleinberg et. al. \cite{Kleinberg1999a,Kleinberg2001} and Faloutsos, Faloutsos and Faloutsos \cite{Faloutsos1999,Siganos2003} measured the degree distribution of the World-Wide Web and independently observed that it is well approximated by a \emph{power-law distribution}, i.e. the number of nodes $y_i$ of a given degree $i$ is proportional to $i^{-\beta}$ where $\beta > 0$.
% This was later verified for a large number of existing real-world networks such as protein-protein interactions, gene regulatory networks, peer-to-peer networks, mobile call networks and social networks \cite{Jovanovic2001,Guelzim2002,Seshadri2008,Eubank2004}.
% In order to analyze these graphs, some research has been directed towards finding suitable models for describing structural properties quantitatively and qualitatively. A number of \emph{\plg} (\PLG) models have been proposed, such as the Barab\'asi-Albert model of \emph{Preferential Attachment} \cite{Barabasi1999}, the \emph{LCD model} \cite{Bollobas2002}, the \emph{Buckley-Osthus model} \cite{Buckley2004}, the \emph{Cooper-Frieze model} \cite{Cooper2003} and the \emph{Copying model} due to Kumar et. al. \cite{Kumar2000}. All these models describe a \emph{random growth process} starting from a small seed graph and yielding---besides other features---a power-law degree distribution in the limit.
% 
% A different approach is to take a power-law degree sequence as input and to generate a graph instance with this distribution in a random fashion. Among the most widely known models of this kind is the \emph{ACL model} due to Aiello, Chung and Lu \cite{Aiello2001}.
% Here, the number $y_i$ of vertices of degree $i$ is roughly given by $y_i \approx e^{\alpha} / i^{\beta}$, where $e^{\alpha}$ is a normalization constant which determines the size of the graph.
% While this model is potentially less accurate than the detailed description of a growth process of an evolving graph, it has the advantage of being robust and general, i.e., structural properties that are true in this model will be true for the majority of graphs with the given degree sequence.
% All of the above models are well motivated and there exists a large body of literature on mathematical foundations, properties and applications \cite{Barabasi1999,Aiello2000,Bollobas2002,Eubank2004,Mihail2006}. In this paper, we focus on the ACL model for random \PLG\ which we will refer to as the \emph{\Mab\ model}.
% 
% Apart from having certain structural properties, such as a power-law degree distribution, high clustering coefficient, small-world characteristics and self similarity, there exists practical evidence that combinatorial optimization in \PLG\ is easier than in general graphs \cite{Park2001,Gkantsidis2003,Eubank2004,Koyuturk2006}.
% Contrasting this Ferrante et. al. \cite{Ferrante2008} and Shen et. al. \cite{Shen2010} studied the approximation hardness of certain optimization problems in \emph{combinatorial \plgs} and showed \NP-hardness and \APX-hardness of classical problems such as \mvc\ (\MVC), \mis\ (\MIS) and \mds\ (\MDS).
% In this paper we study the approximability of the \MVC\ problem in the random \plg\ model of Aiello et. al. \cite{Aiello2001}.

%{\bf Our Results}\hspace{0.2cm} 
\paragraph{Our Results}
In this paper we study the special case of the Graphic TSP when the underlying graph is a power law graph.
We denote the special case as Power Law Graphic TSP. % (PLG-TSP).
For the case when the power law exponent $\beta$ satisfies 
$1<\beta <2.48$ and the graph is connected,
we show that the problem is approximable within $\frac{1}{2}+\frac{\zeta (\beta)}{\max\{2,\zeta (\beta)+1\slash 2\}}$, where $\zeta (\beta)=\sum_{i=1}^{\infty}i^{-\beta}$
is the \emph{Riemann Zeta Function}. 
For $\beta>1.256$, this improves over the current best Graphic TSP upper approximation bound of $\nicefrac{7}{5}$ due to \cite{Sebo2014}.
In particular, for $\beta =1.5$ this yields an approximation ratio of $1.339$. For $\beta =2.5$, the resulting approximation ratio is $1.171$. For $\beta >2.479$, power law graphs are not connected any more.  

Then we consider the $(1,2)$-TSP with underlying power law graph, which we denote as Power Law $(1,2)$-TSP. % (PL-$(1,2)$-TSP). 
For the case $\beta >1$, we obtain an approximation ratio of 
$\frac{\frac{11}{9}\zeta (\beta)+\frac{29}{72}}{\zeta (\beta )+\frac{1}{2}}$.
For $\beta>2.729$ we obtain an improved ratio of $\frac{2\zeta(\beta) + \frac{1}{2}\zeta(\beta-1) -1}{\zeta(\beta)+ \frac{1}{2}}$ which converges to $1$ as $\beta\to\infty$.
For $\beta>1.666$, this improves over the current best $(1,2)$-TSP upper approximation bound of $\nicefrac{8}{7}$ due to \cite{Berman2006}.
For $\beta =1.5$, this yields a $1.155$-approximation and for $\beta =2.5$ a 
$1.109$-approximation. 

In the case when the underlying graph is a random PLG with $\beta>1$, we obtain an improved expected approximation ratio. % separately for the ranges $\beta>2$, $\beta=2$ and $1<\beta<2$.
In the case $1<\beta<2$ and $\beta=2$ this is equal to $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot\frac{5}{4}}{\zeta(\beta)+\frac{5}{4}}$ and $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot\frac{5}{8}}{\zeta(\beta)+\frac{5}{8}}$, respectively.
For $\beta>2$ the expected approximation ratio is $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot E_k}{\zeta(\beta)+E_k}$, where $E_k$ is the expected lower bound on the number of $2$-edges in an optimum tour. % random Power Law $(1,2)$-TSP instance.

%which is equal to $1.076$ for $\beta =2.2$.  
On the other hand we show that for $\beta >1$, the Power Law $(1,2)$-TSP is NP-hard to approximate within approximation ratio $\frac{(\zeta (\beta)+\nicefrac{1}{2})\cdot 3^{\beta -1}\cdot 2\cdot (\beta -1)\cdot 354 +1}{(\zeta (\beta)+\nicefrac{1}{2})\cdot 3^{\beta -1}\cdot 2\cdot (\beta -1)\cdot 354}$.
This gives an approximation lower bound of $1.00086$ for $\beta =1.2$ and of $1.0012$ for $\beta =1.1$.

%\begin{table}[htb]
%\centering
%\caption{Main Results}
%%\renewcommand{\arraystretch}{2}
%\label{tab:Results}
%\begin{tabular}{lcl}
%\toprule
%%\multicolumn{2}{c}{Item} &            \\ \cline{1-2}
%\emph{Problem}               & \emph{Approx. Upper Bound} & \emph{Range} \\ 
%\midrule
%Power Law Graphic TSP & ${\frac{1}{2}+\frac{\zeta (\beta)}{\max\{2,\zeta (\beta)+\frac{1}{2}\}}}$ & $1<\beta<2.479$ \\ 
%Power Law $(1,2)$-TSP & $\frac{\frac{11}{9}\zeta (\beta)+\frac{29}{72}}{\zeta (\beta )+\frac{1}{2}}$ & $\beta>1$ \\
%Power Law $(1,2)$-TSP & $\frac{2\zeta(\beta) + \frac{1}{2}\zeta(\beta-1) -1}{\zeta(\beta)+ \frac{1}{2}}$ & $\beta>2.729$ \\
%Random Power Law $(1,2)$-TSP & $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot E_k}{\zeta(\beta)+E_k}$  & $\beta>2$ \\
%Random Power Law $(1,2)$-TSP & $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot\frac{5}{8}}{\zeta(\beta)+\frac{5}{8}}$ & $\beta=2$ \\
%Random Power Law $(1,2)$-TSP & $\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot\frac{5}{4}}{\zeta(\beta)+\frac{5}{4}}$ & $1<\beta<2$ \\ 
%\bottomrule
%\end{tabular}
%\end{table}

%The paper is organized as follows. 
\paragraph{Organization of the Paper} In \autoref{sec:Methods} we give an outline of the methods and constructions used in the paper. \autoref{sec:Preliminaries} provides the definition of the PLG model due to \cite{Aiello2001} and related notations.
In \autoref{sec:GraphicTSP} we describe our results for the Graphic TSP on power law graphs.
In \autoref{sec:OneTwoTSP} we present our results on the $(1,2)$-TSP with underlying power law graph. \autoref{sec:DeterministicUpper} contains the analysis of the algorithm from \cite{Papadimitriou1993} for deterministic power law graphs. \autoref{sec:AsymptoticUpper} deals with the case of a large power law exponent. In \autoref{sec:RandomUpper} we consider the case when the underlying graph is a random PLG. Approximation lower bounds are given in \autoref{sec:LowerBounds}.

\section{The Method}\label{sec:Methods}

We give first a brief outline of the methods and constructions used in this paper.
For the Graphic TSP with underlying power law graph, we give an improved analysis of the algorithms of Christofides \cite{Christofides1976}, M{\"o}mke-Svensson \cite{Moemke2011} and the algorithm of Mucha \cite{Mucha2012}.
This is based on the analysis of local configurations in PLGs, consisting of a high-degree node and its degree $1$ and $2$ neighbors. We show that any such configuration
contributes to the lower bound for the length of an optimum tour. The same idea also applies to the $(1,2)$-TSP with underlying PLG. 

The approximation hardness results for the $(1,2)$-TSP with underlying PLG are based on efficient embeddings of graphs into power law graphs. 
We start from the lower bound for $(1,2)$-TSP given in \cite{Karpinski2013}. We map the associated graphs to instances which contain a perfect matching. This is then used in order
to embed those graphs into sufficiently small PLGs. 

\section{Preliminaries}\label{sec:Preliminaries}

In this section we first give the formal definition of $(\alpha,\beta)$-power law graphs. Then we provide estimates for 
sizes and volumes of some subsets of the vertex set of a power law graph which we call \emph{intervals}. Later on we make use of 
these estimates in the analysis of our upper and lower bound constructions.
\begin{definition}\cite{Aiello2001}
An undirected multigraph $G=(V,E)$ with self loops is called an $(\alpha,\beta)$ power law graph if the following conditions hold:
\begin{itemize}
\item The maximum degree is $\Delta=\lfloor e^{\alpha\slash\beta}\rfloor$.
\item For $i=1,\ldots , \Delta$, the number $y_i$ of nodes of degree $i$ in $G$ satisfies
      \[y_i = \left\lfloor \frac{e^{\alpha}}{i^{\beta}}\right\rfloor\] 
\end{itemize}
\end{definition}
The following estimates for the number $n$ of vertices of an $(\alpha,\beta)$ power law graph are well known \cite{Aiello2001}:
%%\begin{equation}
\[n\approx \left\{\begin{array}{l@{\quad}l}
 \frac{e^{\alpha\slash\beta}}{1-\beta} & \mbox{for $0<\beta <1$,}\\
 \alpha\cdot e^{\alpha} & \mbox{for $\beta =1$,}\\
 \zeta (\beta )\cdot e^{\alpha} & \mbox{for $\beta >1$.}
\end{array}\right.\quad 
m\approx \left\{\begin{array}{l@{\quad}l}
 \frac{1}{2}\frac{e^{2\alpha\slash\beta}}{2-\beta} & \mbox{for $0<\beta <2$,}\\
 \frac{1}{4}\alpha e^{\alpha} & \mbox{for $\beta =2$,}\\
 \frac{1}{2}\zeta (\beta -1)e^{\alpha} & \mbox{for $\beta >2$.}
\end{array}\right.\]
%%\end{equation}
Here $\zeta (\beta)=\sum_{i=1}^{\infty}i^{-\beta}$ is the {\sl Riemann Zeta Function}.

By \Mab\ we denote the probability distribution on the set \Gab\ which is obtained in the following way \cite{Aiello2001}:
\begin{enumerate}
  \item Generate a set $L$ of $\deg{v}$ distinct copies of each vertex $v$.
  \item Generate a random matching on the elements of $L$.
  \item For each pair of vertices $u$ and $v$, the number of edges joining $u$ and $v$ in $\gab$ is equal to the number of edges in the matching of $L$, which join copies of $u$ to copies of $v$.
\end{enumerate}

\begin{figure}[htb]
\centering
% \tikzsetnextfilename{RandomMatch}%
% \input{RandomMatch}
 \includegraphics[scale=1]{RandomMatch}
 \caption{}
 \label{fig:RandomMatch}
\end{figure}

As in \cite{Aiello2001}, in the following we work with the real numbers $\frac{\e^{\alpha}}{i^{\beta}}$, $\e^{\frac{\alpha}{\beta}}$ instead of their integer counterparts. For $\beta > 2$ the overall error is bounded by $\e^{\frac{\alpha}{\beta}}=o(n)$ (c.f. \cite{Aiello2001}, remark on page 6).

 Given an $(\alpha,\beta)$ power law graph $G=(V,E)$ with $n$ vertices and maximum degree $\Delta$ and two integers $1\leq a\leq b\leq\Delta$, 
 an \emph{interval} $[a,b]$ is defined as the subset of $V$
 \begin{equation*}
 [a,b] = \{v\in V|a\leq \mbox{deg}_G(v)\leq b\}
 \end{equation*}
 If $U\subseteq V$ is a subset of vertices, the \emph{volume} $\mbox{vol}(U)$ of $U$ is defined as the sum of node degrees of nodes in $U$.
% We have the following estimates for sizes and volumes of node intervals in $(\alpha,\beta)$-PLGs.
 In \autoref{sec:GraphicTSP} we will make use of estimates of sizes and volumes of node intervals in $(\alpha,\beta)$-PLGs.
 In particular we will show that in the case $\beta >2$ the volume of a node degree interval of the form 
$[x\Delta,\Delta ]=\{v|x\Delta\leq\mbox{deg}(v)\leq\Delta\}$ is bounded by $ \frac{e^{2\alpha\slash\beta}}{(\beta -2)x^{\beta -2}}$.
% In the case $\beta >2$ the volume of a node degree interval
%$[x\Delta,\Delta ]=\{v|x\Delta\leq\mbox{deg}(v)\leq\Delta\}$ can be estimated as follows:
%\begin{align*}
%\mbox{vol}([x\Delta,\Delta ]) & = \sum_{i=x\Delta}^{\Delta}\left\lfloor\frac{e^{\alpha}}{i^{\beta}}\right\rfloor\cdot i
%    \leq \sum_{i=x\delta}^{\Delta}\frac{e^{\alpha}}{i^{\beta-1}}
%    \leq e^{\alpha}\int_{x\Delta}^{\Delta +1}\frac{1}{x^{\beta -1}}dx + (1-x)\Delta\\ &= (1+o(1))e^{\alpha} \left [\frac{y^{2-\beta}}{2-\beta}\right ]_{x\Delta}^{\Delta +1}
%    = \frac{(1+o(1))\e^{\alpha}}{\beta -2}\left (\frac{1}{(x\Delta)^{\beta -2}}-\frac{1}{(\Delta +1)^{\beta -2}}\right ) \\
%     &\leq   \frac{e^{\alpha-\alpha\cdot\frac{\beta-2}{\beta}}}{(\beta -2)\cdot x^{\beta -2}}
%     =      \frac{e^{2\alpha\slash\beta}}{(\beta -2)x^{\beta -2}}
%\end{align*}


% \begin{theorem}\cite{Gast2015}
% For $0<\beta <1$,
% \[\begin{array}{l@{}c@{}l}
% |[x\Delta,y\Delta ]| & \in & \left [\frac{\Delta}{1-\beta}(y^{1-\beta}-x^{1-\beta})
%                                     -\left (\frac{1}{x^{\beta}}-\frac{1}{y^{\beta}}\right ),
%                                     \frac{\Delta}{1-\beta}(y^{1-\beta}-x^{1-\beta})\right ]\\
% |x\Delta,\Delta]| & \in & \left [\frac{\Delta}{1-\beta}(1-x^{1-\beta})
%                            -\left (\frac{1}{x^{\beta}}-1\right ),
%                            \frac{\Delta}{1-\beta}(1-x^{1-\beta})\right ]\\
% \mbox{vol}([x\Delta,\Delta]) & \geq & \Delta^2\left (\frac{1-x^{2-\beta}}{2-\beta}-\frac{1}{2}+\frac{x^2}{2}\right )
%                                       -\Delta\left (1-x^{1-\beta}-\frac{1}{2}+\frac{x}{2}\right )
% \end{array}\]
% For $\beta=1$,
% \[\begin{array}{l@{}c@{}l}
% |[x\Delta,y\Delta ]| & \in & \left [e^{\alpha}\cdot\left (\ln\left (\frac{1}{x}\right )-\ln\left (\frac{1}{y}\right )\right )-(y-x)e^{\alpha}, 
%                                     e^{\alpha}\cdot\left (\ln\left (\frac{1}{x}\right )-\ln\left (\frac{1}{y}\right )\right )\right ]\\
% \mbox{vol}([x\Delta,y\Delta ]) & \in & \left [e^{\alpha}(y-x)\Delta -\left (\frac{y\Delta (y\Delta +1)}{2}-\frac{x\Delta (x\Delta +1)}{2}\right ),
%                                               e^{\alpha}(y-x)\Delta\right ]
% \end{array}\]
% \end{theorem}
% These estimates will be used in subsequent sections where we construct efficient reductions from the general MIS problem to MIS in $(\alpha,\beta )$-PLGs for $\beta\leq 1$.
% In particular we will be concerned with the embedding of the node degree distribution of a given graph $G$ into an interval of the form $[x\Delta,\Delta ]$ of a 
% power law node degree distribution with parameters $\alpha,\beta$.

Lower.tex
%\section{Lower Bounds}
\subsection{Lower Bounds}\label{sec:LowerBounds}
In this section we give the first approximation lower bounds for TSP in $(1,2)$-PLG instances.
The approximation hardness of the general $(1,2)$-TSP problem was proven in \cite{Papadimitriou1993}.
%For the general $(1,2)$-TSP the possibility of a PTAS was already ruled out by the result of \cite{Papadimitriou1993} together with the PCP-theorem \cite{Arora1998a,Arora1998}. %Two decades 
Later the first explicit inapproximability bounds of $\nicefrac{5381}{5380}$ was proven by \citeauthor{Engebretsen2003} \cite{Engebretsen2003}, and further improved step by step to the current best bound of $\nicefrac{123}{122}$ by \citeauthor{Karpinski2013} \cite{Karpinski2013} applying the results of \citeauthor{Berman1999} \cite{Berman1999}, \cite{Berman2001}.

Our overall approach is to construct appropriate reductions from the $(1,2)$-Metric TSP to 
$(1,2)$-metric instances whose underlying graph is a PLG.
We make use of the lower bound constructions developed in \cite{Karpinski2013b} (see also \cite{Engebretsen2006,Lampis2012,Karpinski2013a,Karpinski2013}).
The reduction in \cite{Karpinski2013b} starts from a special bounded occurrence optimization problem.
%As in \cite{Karpinski2013b} we start with defining a special bounded occurrence optimization problem which plays an important role in our reductions.

\begin{definition}[Hybrid Problem] 
 Given a system of linear equations mod $2$ over $n$ variables, $m_2$
equations with exactly two variables, and $m_3$ equations with exactly three variables, find an assignment to the variables that maximizes the number of satisfied equations.
\end{definition}

The approximation hardness of the above problem was proven by \citeauthor{Berman1999} in \cite{Berman1999} using a result of \citeauthor{Hastad2001} in \cite{Hastad2001}. They proved the following theorem.

\begin{theorem}[\cite{Berman1999}]
 For every $0<\varepsilon<\frac{1}{2}$, there exists an instance $I_H$ of the Hybrid problem with $42v$ variables, $m_2=60v$, $m_3=2v$ such that every variable occurs exactly $3$ times and it is NP-hard to decide whether $I_H$ has its optimum value above $(62-\varepsilon)v$ or below $(61+\varepsilon)v$.
\end{theorem}

The above result is used in the following reduction from Hybrid to Subcubic $(1,2)$-TSP due to \citeauthor{Karpinski2013b} \cite{Karpinski2013b}. Later we present our new reduction from \emph{slightly modified} Subcubic $(1,2)$-TSP instances to $(1,2)$-TSP instances with underlying PLG.

\paragraph{Reduction from Hybrid to Subcubic $(1,2)$-TSP}
The reduction starts from Hybrid instances with $60v$ $2$-equations, $2v$ $3$-equations and $42v$ variables. % $36v$ checker variables and $6v$ contact variables.
In \cite{Karpinski2013b}, these instances have been mapped to $(1,2)$-TSP instances $G_{SC}^{12}$ with 
\[60v\cdot 8+2v\cdot (9\cdot 8+6\cdot 3 +2\cdot 3)=v\cdot 672\]
nodes. Our aim is to modify these instances slightly in order to fit them into a power law degree distribution.
The instances $G_{SC}^{12}$
consist of building blocks called parity gadgets. A parity gadget is a graph $P$ with $8$ nodes being connected as shown in \autoref{fig:Parity}.

\begin{figure}[htb]
 \centering
% \tikzsetnextfilename{Parity}%
% \input{Parity}
 \includegraphics[scale=1]{Parity}
 \caption{Parity gadget.}
 \label{fig:Parity}
\end{figure}

The graph $G_{SC}^{12}$ contains 
\begin{itemize}
\item one parity gadget for every variable,
\item one additional parity gadget for every $2$-equation,
\item for every $3$-equation a subgraph involving the parity gadgets for the variables being involved,
      additionally $6$ parity gadgets and $12$ extra nodes.
\end{itemize}

Let us describe the simulating gadget for a $3$-equation $x\oplus y\oplus z=0$, as constructed in \cite{Karpinski2013b}. Given an equation of the form $x\oplus y\oplus z=0$, three clauses $(x\vee a_1 \vee a_2)$, $(y\vee a_2 \vee a_3)$ and $(z\vee a_1 \vee a_3)$ are created. Note that for any given assignment to $x$, $y$ and $z$ satisfying the equation mod $2$, it is possible to find an assignment of $a_1$, $a_2$ and $a_3$ that satisfies all clauses. Otherwise any assignment to $a_1$, $a_2$ and $a_3$ satisfies at most two clauses. The clause gadget as constructed in \cite{Karpinski2013b} is shown in \autoref{fig:G3v}.

\begin{figure}[htb]
 \centering
% \tikzsetnextfilename{DetailedG3v}%
% \input{DetailedG3v}\quad\vrule\quad%\raisebox{2cm}{$\quad\mapsto\quad$}
% \tikzsetnextfilename{ModularG3v}%
% \input{ModularG3v}
 \includegraphics[scale=1]{DetailedG3v}\quad\vrule\quad
 \includegraphics[scale=1]{ModularG3v}
% \caption{Equation gadget for $x\oplus y\oplus z=0$ in detailed and modular view.}
 \caption{The gadget corresponding to clauses $(x\vee y\vee z)$ in detailed and modular view.}
 \label{fig:G3v}
\end{figure}

In order to complete the construction for an equation $x\oplus y\oplus z =0$, \cite{Karpinski2013b} introduced a gadget to simulate equations of the form $a_1^1\oplus a_1^2=0$. The construction is shown in \autoref{fig:Chain}.

\begin{figure}[htb]
 \centering
% \tikzsetnextfilename{Chain}%
% \input{Chain}
 \includegraphics[scale=1]{Chain}
 \caption{Modular view of the gadget simulating $x\oplus y\oplus z=0$.}
 \label{fig:Chain}
\end{figure}

This completes the modular description of the reduction of Hybrid instances $I_H$ to Subcubic $(1,2)$-TSP instances $G_{SC}^{12}$. For further details we refer to  \cite{Karpinski2013b}.

\paragraph{Subcubic $(1,2)$-TSP and Perfect Matchings}
Next, we modify the above instances $G_{SC}^{12}$ to permit a \emph{perfect matching} in order to prepare our reduction to $(1,2)$-TSP instances with underlying PLG.
%We show that Subcubic $(1,2)$-TSP instances $G_{SC}^{12}$ can be slightly modified to permit a \emph{perfect matching}. 
First we observe that the subgraphs corresponding to parity gadgets (cf. \autoref{fig:Parity}) and the subgraphs corresponding to equations of the form $x\oplus y=0$ already contain a perfect matching.

Now we consider the clause gadget simulating $(x\vee y \vee z)$ as shown in \autoref{fig:G3v}.
It uses three isomorphic copies of a parity gadget and contains $6$ extra nodes, namely $s_\vee$, $s_{mid},$ $e_\vee$, $c_1$, $c_2$ and $c_3$ (cf. \autoref{fig:G3v}).
These extra nodes are of degree $3$. If we replace two such extra nodes $v$ by a separate copy of the graph $K_4$ and connect three of the four nodes 
to the neighbors of $v$ as shown in \autoref{fig:MatchingG3v}, then the resulting modified gadget has the additional property that it contains a perfect matching.

\begin{figure}[htb]
 \centering
% \tikzsetnextfilename{ModularG3v_new}%
% \input{ModularG3v_new}\raisebox{2.2cm}{$\,\mapsto\,$}
% \tikzsetnextfilename{ModularG3v_match}
% \input{ModularG3v_match}
 \includegraphics[scale=1]{ModularG3v_new}\raisebox{2.2cm}{$\quad\mapsto\quad$}
 \includegraphics[scale=1]{ModularG3v_match}
 \caption{The modified gadget for clauses $(x\vee y\vee z)$ that contains a perfect matching.}
 \label{fig:MatchingG3v}
\end{figure}

If we let $\tilde{G}_{SC}^{12}$ the graph which is obtained from $G_{SC}^{12}$ by applying all these modifications, then we conclude that 
$\tilde{G}_{SC}^{12}$ contains a perfect matching which we denote as $M$. 

The modified instances $\tilde{G}_{SC}^{12}$ have $2\cdot (60v+2v\cdot 9)=156v$ nodes of degree $2$, $6\cdot (60v+2v\cdot 9)+2v\cdot (6\cdot 3+6)=516v$ nodes of degree $3$ 
and $3\cdot2\cdot \sharp G_v=3\cdot 6\cdot 2v=36v$ nodes of degree $4$.

Thus we have a mapping
\[\begin{array}{c@{}c@{}c@{}c@{}c}
\mbox{Hybrid} & \longrightarrow & \mbox{Subcubic $(1,2)$-TSP} & \longrightarrow & \mbox{$(1,2)$-TSP}\\[1.2ex]
I_H & \longmapsto & G_{SC}^{12} & \longmapsto & \tilde{G}_{SC}^{12}
\end{array}\]
where $\tilde{G}_{SC}^{12}$ is a graph of maximum degree $4$.
The resulting instance $\tilde{G}_{SC}^{12}$ has $708v$ vertices, namely $156v$ of degree $2$, $516$ of degree $3$ and $36v$ of degree $4$.
It is hard to decide if $\tau\geq 709v$ or $\tau\leq 708v$.

\paragraph{Reduction to Power Law $(1,2)$-TSP}
Now those instances have to be embedded into power law graphs. The instance $\tilde{G}_{SC}^{12}$ has a perfect matching $M$, which we want to use in order to embed
$\tilde{G}_{SC}^{12}$ into a power law graph. Thus we have to give a precise description of the node degrees of pairs of nodes which are connected by matching edges.
Let us make use of the following notation: We say an edge $e$ is of type $(a,b)$ if $e=\{u,v\}$, the degree of $u$ is $a$ and the degree of $v$ is $b$.
We observe that inside each parity gadget $P$, $M$ contains $2$ edges of type $(3,3)$ and $2$ edges of type $(2,3)$.

Moreover, $M$ contains for every $3$-equation $2\cdot 3+3$ edges of type $(3,3)$, $2\cdot 3$ edges of type $(3,4)$ and $2\cdot 3$ edges of type $(4,4)$.

Thus in total $M$ consists of the following edges:
\begin{itemize}
\item edges of type $(2,3)$: $2\cdot\sharp P=2\cdot (2v\cdot 9+60v)=2\cdot 78v=156v$
\item edges of type $(3,3)$: $2\cdot\sharp P+9\cdot\sharp\mbox{3-eq}=18v+2\cdot 78v=174v$
\item edges of type $(3,4)$: $6\cdot\sharp\mbox{3-eq}=12v$
\item edges of type $(4,4)$: $6\cdot\sharp\mbox{3-eq}=12v$ 
\end{itemize}  

We want to embed  $\tilde{G}_{SC}^{12}$ into an interval $[\delta ,\Delta ]$ of a power law distribution, where $\delta$ is a parameter of this construction.
In order to fit $\tilde{G}_{SC}^{12}$ into $[\delta ,\Delta ]$, we replace the edges of $M$ by multi-edges. Let $\mu\colon M\to {\mathbb N}$ such that 
for $e\in M$, $\mu (e)$ is the multiplicity of edge $e$. 

Let us first consider the special case when $\mu\colon M\to\{1\}$. In that case, we have to minimize $\alpha$ such as to satisfy the following inequalities: 
\[156v\leq\frac{e^{\alpha}}{2^{\beta}},\quad (156+174\cdot 2+12)v\leq\frac{e^{\alpha}}{3^{\beta}},\quad (12+2\cdot 12)v\leq\frac{e^{\alpha}}{4^{\beta}},\]
or equivalently
$e^{\alpha}\geq\max\{2^{\beta}\cdot 156v, 3^{\beta}\cdot 516v, 4^{\beta}\cdot 36v\}$.
We first observe that 
for $\beta\leq\frac{\log\left (\frac{516}{36}\right )}{\log (\frac{4}{3})}$, this is equivalent to $e^{\alpha}\geq 3^{\beta}\cdot 516v$.
Suppose now that we have chosen $\alpha$ such that $\zeta (\beta)e^{\alpha}=\zeta (\beta)\cdot 3^{\beta}\cdot 516v$.
The power law graph $G_{\alpha,\beta}$ is the union of $\mu (\tilde{G}_{SC}^{12})$, a matching $W_1$ on all but at most one degree $1$ nodes and a graph $W$ consisting of the remaining nodes of degree at least $2$ and at most one degree-$1$ node. % is attached.
The graph $W$ can be constructed in such a way that it contains a TSP path consisting of edges of cost one (cf. \cite{Gast2015}).
Let $|W|$ denote the number of nodes in the graph $W$.
Then we may assume every tour $\tau$ of the $(1,2)$-metric space defined by $G_{\alpha,\beta}$ to consist of a TSP path $\tau_{SC}$ of $\tilde{G}_{SC}^{12}$, a path in $W$ and a path of cost at most $\frac{3}{2}\cdot\e^{\alpha}-1$ connecting the degree-$1$ nodes in $W_1$ and three edges of cost $2$ connecting these paths. % attached to $W$ and two edges of cost $2$ connecting these two paths.
The cost of the TSP path in $W$ is asymptotically equal to $|W|-1$. Thus the cost of the tour $\tau$ satisfies
\[c(\tau) = c(\tau_{SC})+|W|+\frac{3}{2}e^{\alpha}+O(1).\] 
We have $|\tilde{G}_{SC}^{12}|=708v=708\cdot\frac{\zeta (\beta)e^{\alpha}}{\zeta (\beta)\cdot 3^{\beta}\cdot 516}$ and
\[|W|=\left (\zeta (\beta )-1-\frac{708}{516\cdot 3^{\beta}}\right )e^{\alpha}\]
Thus it is NP-hard to decide if the cost of an optimum tour $\tau^*$ in $G_{\alpha,\beta}$ satisfies
\[c(\tau^*)\leq 708\cdot\frac{e^{\alpha}}{3^{\beta}\cdot 516}+\left (\zeta (\beta )-1-\frac{708}{516\cdot 3^{\beta}}\right )e^{\alpha}+\frac{3}{2}\cdot e^{\alpha}+O(1)\]
or
\[c(\tau^*)\geq 709\cdot\frac{e^{\alpha}}{3^{\beta}\cdot 516}+\left (\zeta (\beta )+\frac{1}{2}-\frac{708}{516\cdot 3^{\beta}}\right )e^{\alpha}-O(1).\]

For $\beta\geq\frac{\log\left (\frac{516}{36}\right )}{\log (\frac{4}{3})}$, we obtain the requirement $e^{\alpha}\geq 4^{\beta}\cdot 36v$ and proceed in the same way.
We obtain the following result.
%\begin{theorem}\label{thm:LowerOne}
%For $1<\beta\leq\frac{\log\left (\frac{516}{36}\right )}{\log (\frac{4}{3})}$, the $(1,2)$-TSP on $(\alpha,\beta )$-Power Law Graphs is NP-hard to approximate within
%any factor less than $\frac{3^{\beta}\cdot 516\cdot (\zeta (\beta)+1)+1}{3^{\beta}\cdot 516\cdot (\zeta (\beta)+1)}$.
%\end{theorem}
\begin{theorem}\label{thm:LowerOne}
For $1<\beta\leq\frac{\log\left (\frac{516}{36}\right )}{\log (\frac{4}{3})}$, the $(1,2)$-TSP on $(\alpha,\beta )$-Power Law Graphs is NP-hard to approximate within
any factor less than $\frac{3^{\beta}\cdot 516\cdot (\zeta (\beta)+\nicefrac{1}{2})+1}{3^{\beta}\cdot 516\cdot (\zeta (\beta)+\nicefrac{1}{2})}$.

For $\beta\geq\frac{\log\left (\frac{516}{36}\right )}{\log (\frac{4}{3})}$, the $(1,2)$-TSP on $(\alpha,\beta )$-Power Law Graphs is NP-hard to approximate within
any factor less than $\frac{4^{\beta}\cdot 36\cdot (\zeta (\beta)+\nicefrac{1}{2})+1}{4^{\beta}\cdot 36\cdot (\zeta (\beta)+\nicefrac{1}{2})}$.% for .
\end{theorem}

Now we improve on this result and consider the general case when $\mu\colon M\to {\mathbb N}$. We consider an embedding which we call
\emph{Even-Degree Packing} for a given $\alpha$. We choose edge multiplicities $\mu (e)$ for $e=\{u,v\}$ such that when $d(u)+\mu(e)-1\leq d(v)+\mu(e)-1\leq d(u)+\mu (e)$,
then $d(u)+\mu(e)-1$ is even. This means that we partition the interval $[2,\Delta ]$ into subintervals of size $2$ of the form $[2i,2i+1]$ and construct the edge multiplicities
$\mu$ in such a way that we always have $\mu (e)\equiv d(u)-1 \mod 2$. Suppose the degrees which are occupied in this way are of the form $2i,1\leq i\leq x\Delta$.
Then the sum of multiplicities of edges which we can pack in this way is
\begin{align*}
\sum_{i=1}^{x\Delta}\left\lfloor\frac{e^{\alpha}}{(2i+1)^{\beta}}\right\rfloor
 & \geq    \sum_{i=1}^{x\Delta}\frac{e^{\alpha}}{(2i+1)^{\beta}} -x\Delta\\
 & \geq \int_{1}^{x\Delta+1}\frac{e^{\alpha}}{(2y+1)^{\beta}}dy -x\Delta
 = \frac{e^{\alpha}}{2(\beta -1)}\left (3^{1-\beta}-(2x\Delta+3)^{1-\beta} \right )-x\Delta
\end{align*}
with $x\leq\frac{1}{2}\cdot\frac{\Delta -1}{\Delta}$. Thus it suffices to choose $\alpha$ such that 
$\frac{e^{\alpha}}{2(\beta -1)}\cdot \frac{1}{3^{\beta -1}}-x\Delta\geq 354v$. For $x=\frac{1}{2}\cdot\frac{\Delta -1}{\Delta}$, this is equivalent to
\[\frac{e^{\alpha}}{3^{\beta -1}\cdot 2(\beta -1)}-\frac{1}{2}\cdot (e^{\alpha})^{1\slash\beta}+\frac{1}{2}\geq 354v\]
Now the cost of a tour $\tau$ is $c(\tau )=c(\tau_{SC})+|W|+\frac{3}{2}e^{\alpha}+3$, and we have 
$|\tilde{G}_{SC}^{12}|=708v=708\cdot\frac{e^{\alpha}}{3^{\beta -1}\cdot 2(\beta -1)\cdot 354}$. The size of the set $W$ is given as
\[|W|=(\zeta (\beta)-1)e^{\alpha}-|\tilde{G}_{SC}^{12}|=\left (\zeta (\beta)-1-\frac{708}{3^{\beta -1}\cdot 2(\beta -1)\cdot 354}\right )\]
Thus it is NP-hard to decide if
\[c(\tau^*)\leq 708\cdot \frac{e^{\alpha}}{3^{\beta -1}\cdot 2(\beta -1)\cdot 354}
                +\left (\zeta (\beta )-1-\frac{708}{3^{\beta -1}\cdot 2(\beta -1)\cdot 354}\right )e^{\alpha}+\frac{3}{2}e^{\alpha}+O(1)\]
or
\[c(\tau^*)\geq 709\cdot \frac{e^{\alpha}}{3^{\beta -1}\cdot 2(\beta -1)\cdot 354}
                +\left (\zeta (\beta )+\frac{1}{2}-\frac{708}{3^{\beta -1}\cdot 2(\beta -1)\cdot 354}\right )e^{\alpha}-O(1)\]
                
We obtain the following result.
\begin{theorem}\label{thm:LowerTwo}
%For $1<\beta\leq\frac{\log\left (\frac{516}{36}\right )}{\log (\frac{4}{3})}$, 
The (1,2)-TSP on $(\alpha,\beta )$-Power Law Graphs is NP-hard to approximate within
any factor less than $\frac{(\zeta (\beta)+\nicefrac{1}{2})\cdot 3^{\beta -1}\cdot 2(\beta -1)\cdot 354+1}{(\zeta (\beta)+\nicefrac{1}{2})\cdot 3^{\beta -1}\cdot 2(\beta -1)\cdot 354}$.
\end{theorem}

In \autoref{fig:PlotLowerBound} we plot and compare the resulting lower bounds of \autoref{thm:LowerOne} and \autoref{thm:LowerTwo} for the $(1,2)$-TSP with underlying $(\alpha,\beta )$-PLG.

\begin{figure}[htb]
 \centering
  \input{PlotLowerBound}
  \caption{Plot of the lower bounds due to \autoref{thm:LowerOne} and \autoref{thm:LowerTwo}.}
  \label{fig:PlotLowerBound}
\end{figure}

%\begin{figure}[htb]
%  \input{PlotLowerBound2}
%  \caption{Plot of the lower bounds due to \autoref{thm:LowerOne} and \autoref{thm:LowerTwo}.}
%  \label{fig:PlotLowerBound2}
%\end{figure}

%The resulting approximation lower bound is
%\[\frac{(\zeta (\beta)+1)\cdot 3^{\beta -1}\cdot 2(\beta -1)\cdot 354+1}{(\zeta (\beta)+1)\cdot 3^{\beta -1}\cdot 2(\beta -1)\cdot 354}\]

mypreambel.tex
\usepackage[utf8]{inputenc}

\usepackage{geometry}

\usepackage{pgf}
\usepackage{nicefrac}
\usepackage{booktabs}
% \usepackage{stmaryrd}
\usepackage{fullpage}
%\usepackage{tikz}
%\usetikzlibrary{automata,arrows,calc,chains,decorations.pathreplacing,decorations.text,decorations.pathmorphing,external}
%
%\tikzexternalize%[prefix=figures/]
%
%\pgfdeclarelayer{edgelayer}
%\pgfdeclarelayer{nodelayer}
%\pgfsetlayers{edgelayer,nodelayer,main}
%
%\tikzset{vertex/.style={draw,shading=ball,ball color=black,circle, inner sep=0pt, minimum size=5pt}}
%\tikzset{vertex2/.style={draw,shading=ball,ball color=black!25,circle,  inner sep=0pt, minimum size=5pt}}


%\usepackage{lscape}
\usepackage[]{asymptote}
% \usepackage{sagetex}
% \usepackage{pgfplots}
% \pgfplotsset{compat=1.12}

\usepackage[%
	%final,
	%draft % do not include images (faster)
]{graphicx}

\usepackage[
   centertags, % (default) center tags vertically
   %tbtags,    % 'Top-or-bottom tags': For a split equation, place equation numbers level
               % with the last (resp. first) line, if numbers are on the right (resp. left).
   sumlimits,  %(default) Place the subscripts and superscripts of summation
               % symbols above and below
   %nosumlimits, % Always place the subscripts and superscripts of summation-type
               % symbols to the side, even in displayed equations.
   intlimits,  % Like sumlimits, but for integral symbols.
   %nointlimits, % (default) Opposite of intlimits.
   namelimits, % (default) Like sumlimits, but for certain 'operator names' such as
               % det, inf, lim, max, min, that traditionally have subscripts placed underneath
               % when they occur in a displayed equation.
   %nonamelimits, % Opposite of namelimits.
   %leqno,     % Place equation numbers on the left.
   %reqno,     % Place equation numbers on the right.
   fleqn,     % Position equations at a fixed indent from the left margin
   			  % rather than centered in the text column.
]{amsmath} %
% eqnarray nicht zusammen mit amsmath benutzen, siehe l2tabu.pdf f�r
% Hintergruende.

\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathtools}
% \usepackage{icomma}
% \usepackage{pifont,amsfonts,amstext}

\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[%
	%german,
	english
]{nomencl}

% \IfDefined{definecolor}{%
% Farbe der Ueberschriften
%\definecolor{sectioncolor}{RGB}{0, 51, 153} % Blau
%\definecolor{sectioncolor}{RGB}{0, 25, 152}    % Blau (dunkler))
\definecolor{sectioncolor}{RGB}{0, 0, 0}    % Schwarz
%
% Farbe des Textes
\definecolor{textcolor}{RGB}{0, 0, 0}        % Schwarz
%
% Farbe fuer grau hinterlegte Boxen (fuer Paket framed.sty)
\definecolor{shadecolor}{gray}{0.90}
% Farben fuer die Links im PDF
\definecolor{pdfurlcolor}{rgb}{0,0,0.6}
\definecolor{pdffilecolor}{rgb}{0.7,0,0}
\definecolor{pdflinkcolor}{rgb}{0,0,0.6}
\definecolor{pdfcitecolor}{rgb}{0,0,0.6}
%% PDF-Linkfarben auf schwarz f�r den Druck:
% \definecolor{pdfurlcolor}{rgb}{0,0,0}
% \definecolor{pdffilecolor}{rgb}{0,0,0}
% \definecolor{pdflinkcolor}{rgb}{0,0,0}
% \definecolor{pdfcitecolor}{rgb}{0,0,0}
% Farben fuer Listings
\colorlet{stringcolor}{green!40!black!100}
\colorlet{commencolor}{blue!0!black!100}

\setcounter{secnumdepth}{2}    % Abbildungsnummerierung mit groesserer Tiefe
\setcounter{tocdepth}{2}		 % Inhaltsverzeichnis mit groesserer Tiefe
% \setcounter{lofdepth}{1}  %1 = nur figures, 2 = figures + subfigures

% \usepackage[%
% 	expansion=true, % better typography, but with much larger PDF file.
% 	protrusion=true
% ]{microtype}

\usepackage{aliascnt}

% \usepackage[%
% 	%round,	%(default) for round parentheses;
% 	square,	% for square brackets;
% 	%curly,	% for curly braces;
% 	%angle,	% for angle brackets;
% 	%colon,	% (default) to separate multiple citations with colons;
% 	comma,	% to use commas as separaters;
% 	%authoryear,% (default) for author-year citations;
% 	numbers,	% for numerical citations;
% 	%super,	% for superscripted numerical citations, as in Nature;
% 	sort,		% orders multiple citations into the sequence in which they appear in the list of references;
% 	sort&compress,    % as sort but in addition multiple numerical citations
%                   % are compressed if possible (as 3-6, 15);
% 	%longnamesfirst,  % makes the first citation of any reference the equivalent of
%                   % the starred variant (full author list) and subsequent citations
%                   %normal (abbreviated list);
% 	%sectionbib,      % redefines \thebibliography to issue \section* instead of \chapter*;
%                   % valid only for classes with a \chapter command;
%                   % to be used with the chapterbib package;
% 	%nonamebreak,     % keeps all the authors names in a citation on one line;
%                   %causes overfull hboxes but helps with some hyperref problems.
% \usepackage{natbib}
% \bibliographystyle{abbrv}
% \bibliographystyle{alpha}
% \bibliographystyle{apalike}
\usepackage[natbib=true,
	    bibencoding=utf8,
	    sorting=nyt,
% 	    style=authoryear,
%             bibstyle=authoryear,
%             citestyle=authoryear,
	    style=alphabetic,
%             bibstyle=alphabetic,
%             citestyle=alphabetic,
	    useprefix=true,
            hyperref=true,
            backref=false,
	    backrefstyle=none,
	    alldates=short,
            abbreviate=true,
%	    url=false,
	    isbn=false,
	    doi=false,
% 	    arxiv=pdf,
	    firstinits=true,
	    maxbibnames=99,
	    backend=biber]{biblatex}
	    
%\DeclareCiteCommand*{\citeauthor}
%{\defcounter{maxnames}{99}%
%\defcounter{minnames}{99}%
%\defcounter{uniquename}{2}%
%\boolfalse{citetracker}%
%\boolfalse{pagetracker}%
%\usebibmacro{prenote}}
%{\ifciteindex{\indexnames{labelname}}{}%
%\printnames{labelname}}
%{\multicitedelim}
%{\usebibmacro{postnote}}

%short command to indicate to biblatex that a certain entry needs its URL displayed.
\DeclareBibliographyCategory{needsurl}
\newcommand{\entryneedsurl}[1]{\addtocategory{needsurl}{#1}}
\renewbibmacro*{url+urldate}{%
  \ifcategory{needsurl}{
    \printfield{url}%
    \iffieldundef{urlyear}
      {}
      {\setunit*{\addspace}%
       \printurldate}}
    {}}


% suppress "In:" before journal or booktitle
\renewbibmacro{in:}{}
% \renewbibmacro{in:}{%
%   \ifentrytype{article}{}{%
%   \printtext{\bibstring{in}\intitlepunct}}}

\begin{filecontents}{Taxonomy.bib}
@misc{Taxonomy2015,
shorthand = {AT15},
author = {},
title = {{Approximation Taxonomy of Metric TSP}},
url = {http://theory.cs.uni-bonn.de/info5/tsp/},
urldate = {2015-08-25},
keyword = {AT},
year = {2015}
}
\end{filecontents}

% \addbibresource[location=remote]{http://dl.dropbox.com/u/6078128/library.bib}
\addbibresource[]{\jobname.bib}
\addbibresource[]{Taxonomy.bib}

\theoremstyle{plain}% default
 
\newtheorem{theorem}{Theorem}  
 
\newaliascnt{lemma}{theorem}  
\newtheorem{lemma}[lemma]{Lemma}  
\aliascntresetthe{lemma}
 
\providecommand*{\lemmaautorefname}{Lemma}

\newtheorem*{theorem*}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem*{corollary}{Corollary}

\theoremstyle{definition}
%\newtheorem{prob}{Problem}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{conj}{Conjecture}[section]
\newtheorem{exmp}{Example}[section]

\theoremstyle{remark}
\newtheorem*{rem}{Remark}
\newtheorem*{note}{Note}
\newtheorem{case}{Case}

\usepackage[
  % Farben fuer die Links
  colorlinks=true,         % Links erhalten Farben statt Kaeten
  urlcolor=pdfurlcolor,    % \href{...}{...} external (URL)
  filecolor=pdffilecolor,  % \href{...} local file
  linkcolor=pdflinkcolor,  %\ref{...} and \pageref{...}
  citecolor=pdfcitecolor,  %
  % Links
%  raiselinks=true,			 % calculate real height of the link
%  breaklinks,              % Links berstehen Zeilenumbruch
  %backref=page,            % Backlinks im Literaturverzeichnis (section, slide, page, none)
  %pagebackref=true,        % Backlinks im Literaturverzeichnis mit Seitenangabe
%  verbose,
%  hyperindex=true,         % backlinkex index
%  linktocpage=true,        % Inhaltsverzeichnis verlinkt Seiten
%  hyperfootnotes=false,     % Keine Links auf Fussnoten
  % Bookmarks
%  bookmarks=true,          % Erzeugung von Bookmarks fuer PDF-Viewer
%  bookmarksopenlevel=1,    % Gliederungstiefe der Bookmarks
%  bookmarksopen=true,      % Expandierte Untermenues in Bookmarks
%  bookmarksnumbered=true,  % Nummerierung der Bookmarks
%  bookmarkstype=toc,       % Art der Verzeichnisses
  % Anchors
%  plainpages=false,        % Anchors even on plain pages ?
%  pageanchor=true,         % Pages are linkable
  % PDF Informationen
%   pdftitle={},             % Titel
%   pdfauthor={},            % Autor
%   pdfcreator={LaTeX, hyperref, KOMA-Script}, % Ersteller
%   %pdfproducer={pdfeTeX 1.10b-2.1} %Produzent
%   pdfdisplaydoctitle=true, % Dokumententitel statt Dateiname im Fenstertitel
%   pdfstartview=FitH,       % Dokument wird Fit Width geaefnet
%   pdfpagemode=UseOutlines, % Bookmarks im Viewer anzeigen
%   pdfpagelabels=true,           % set PDF page labels
%   pdfpagelayout=TwoPageRight, % zweiseitige Darstellung: ungerade Seiten
  									 % rechts im PDF-Viewer
  %pdfpagelayout=SinglePage, % einseitige Darstellung
]{hyperref}

% \usepackage{sidecap}
%\usepackage[ruled,vlined]{algorithm2e}%[2005/10/04]
%---
% Languagesetting
\usepackage{csquotes}
\usepackage[
%	german,
%	ngerman,
	english,
%	french,
]{babel}
\pdfminorversion=5

\def\sectionautorefname{Section}%
\def\subsectionautorefname{Section}%
\def\subsubsectionautorefname{Section}%
\def\algocfautorefname{Algorithm}



\DeclareMathOperator{\e}{e}

\newcommand{\E}{\mathbb{E}}
\newcommand{\deltamax}[1]{\ensuremath{\delta_{\max}(#1)}}
\renewcommand{\deg}[1]{\ensuremath{d(#1)}}
\newcommand{\gab}{\ensuremath{G_{\alpha,\beta}}}%{\ensuremath{G}}%
\newcommand{\Gab}{\ensuremath{\mathcal{G}_{\alpha,\beta}}}
\newcommand{\Mab}{\ensuremath{P(\alpha,\beta)}}
\newcommand{\plg}{power-law graph}
\newcommand{\plgs}{power-law graphs}
\newcommand{\dmax}{\ensuremath{\Delta}}

\newcommand{\floor}[1]{\left\lfloor {#1} \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil {#1} \right\rceil}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\newcommand{\restrict}{\!\restriction\!}
PlotGraphTSP.tex
\begin{asy}
 defaultpen(fontsize(11));
 import graph;
 import gsl;
     size(13cm,9cm,IgnoreAspect);
     

     pen dashed=linetype(new real[] {4,4});
     pen p=linewidth(.75);

     real f(real x) {return 2*zeta(x)/(max(zeta(x)+0.5,2));}
     real g(real x) {return (0.5+(zeta(x))/(max(2,zeta(x)+0.5)));}
     real h(real x) {return 7/5;}
 //     real m(real x) {return (2*zeta(x-1)/3+2*zeta(x)/3+5/6)/(max(2.0,zeta(x)+0.5));}
 //    real m(real x) {return (2*zeta(x-1)/3+2*zeta(x)/3+1/6)/(zeta(x)+0.5);}
     real m(real x) {return (2*zeta(x-1)/3+2*zeta(x)/3+5/6-(2/3)*((x-2)*(zeta(x-1)/2-zeta(x)+1))^((x-1)/(x-2))/(x-1))/(max(2.0,zeta(x)+0.5));}

     real mu(real x) {return (10/9+zeta(x)/(3*max(2,zeta(x)+0.5)));}
  
 //     draw("$f=\frac{2\zeta(\beta)}{\max\{\zeta(\beta)+0.5,2\}}$",graph(f,1.5,3.5),p);
     draw("MST",graph(f,1.25,2.48),p);
     draw("Chr",graph(g,1.25,2.48),p);
     draw("",graph(h,1.25,2.48),dotted+p);
 //    draw("$\frac{\frac{2}{3}\zeta(\beta -1)+\frac{2}{3}\zeta(\beta)+\frac{5}{6}-H_{\beta}}{\max\{\zeta(\beta)+\frac{1}{2},2\}}$",graph(m,2.5,3.5),dotted+p);
     draw("M-S",graph(m,2.4,2.48),dashed+p);
     draw("Mu",graph(mu,1.25,2.48),dashed+p);
     
 //    ylimits(1.968,2);
     xlimits(1.25,2.5);
     label("$\frac{7}{5}$",(2.5,7/5),E);
     xaxis("$\beta$",BottomTop,LeftTicks);
     yaxis("approx. ratio",LeftRight,RightTicks);

     //attach(legend(),(point(S).x,truepoint(S).y),10S,UnFill);
  \end{asy}

PlotLowerBound2.tex
\begin{asy}
 defaultpen(fontsize(11));
 import graph;
 import gsl;
     size(13cm,9cm,IgnoreAspect);
     

     pen dashed=linetype(new real[] {4,4});
     pen p=linewidth(.75);

     //real f(real x) {return (3^(x)*516*(zeta(x)+1)+1)/(3^(x)*516*(zeta(x)+1));}
     real f(real x) {return (3^(x)*516*(zeta(x)+1/2)+1)/(3^(x)*516*(zeta(x)+1/2));}
     pair F(real x) {return (x,f(x));}
     //real g(real x) {return ((zeta(x)+1)*3^(x-1)*2(x-1)*354+1)/((zeta(x)+1)*3^(x-1)*2(x-1)*354);}
     real g(real x) {return (4^(x)*36*(zeta(x)+1/2)+1)/(4^(x)*36*(zeta(x)+1/2));}
     pair G(real x) {return (x,g(x));}
     //real h(real x) {return 535/534;}
  
     draw("$$",graph(f,1.1,9.5),p);
     draw("$$",graph(g,1.1,9.5),dashed+p);
     //draw("$$",graph(h,1.1,3),dotted+p);
     //draw("$$",graph(i,1.1,3),dotted+p);
     //draw("$\frac{535}{534}$",graph(h,1.1,3),dotted+p);
     
 //    ylimits(1.968,2);
     xaxis("$\beta$",BottomTop,LeftTicks);
     yaxis("lower bound",LeftRight,RightTicks);
     //label("$\frac{3^{\beta}\cdot 516\cdot (\zeta (\beta)+\frac{1}{2})+1}{3^{\beta}\cdot 516\cdot (\zeta (\beta)+\frac{1}{2})}$",F(1.5),N);
     //label("$\frac{(\zeta (\beta)+\frac{1}{2})\cdot 3^{\beta -1}\cdot 2(\beta -1)\cdot 354+1}{(\zeta (\beta)+\frac{1}{2})\cdot 3^{\beta -1}\cdot 2(\beta -1)\cdot 354}$",G(1.75),NE);

     //attach(legend(),(point(S).x,truepoint(S).y),10S,UnFill);
  \end{asy}

PlotLowerBound.tex
\begin{asy}
 defaultpen(fontsize(11));
 import graph;
 import gsl;
     size(13cm,9cm,IgnoreAspect);
     

     pen dashed=linetype(new real[] {4,4});
     pen p=linewidth(.75);

     //real f(real x) {return (3^(x)*516*(zeta(x)+1)+1)/(3^(x)*516*(zeta(x)+1));}
     real f(real x) {return (3^(x)*516*(zeta(x)+1/2)+1)/(3^(x)*516*(zeta(x)+1/2));}
     pair F(real x) {return (x,f(x));}
     //real g(real x) {return ((zeta(x)+1)*3^(x-1)*2(x-1)*354+1)/((zeta(x)+1)*3^(x-1)*2(x-1)*354);}
     real g(real x) {return ((zeta(x)+1/2)*3^(x-1)*2(x-1)*354+1)/((zeta(x)+1/2)*3^(x-1)*2(x-1)*354);}
     pair G(real x) {return (x,g(x));}
     //real h(real x) {return 535/534;}
  
     draw("$$",graph(f,1.1,3),p);
     draw("$$",graph(g,1.1,3),dashed+p);
     //draw("$$",graph(h,1.1,3),dotted+p);
     //draw("$$",graph(i,1.1,3),dotted+p);
     //draw("$\frac{535}{534}$",graph(h,1.1,3),dotted+p);
     
 //    ylimits(1.968,2);
     xaxis("$\beta$",BottomTop,LeftTicks);
     yaxis("lower bound",LeftRight,RightTicks);
     label("$\frac{3^{\beta}\cdot 516\cdot (\zeta (\beta)+\frac{1}{2})+1}{3^{\beta}\cdot 516\cdot (\zeta (\beta)+\frac{1}{2})}$",F(1.5),N);
     label("$\frac{(\zeta (\beta)+\frac{1}{2})\cdot 3^{\beta -1}\cdot 2(\beta -1)\cdot 354+1}{(\zeta (\beta)+\frac{1}{2})\cdot 3^{\beta -1}\cdot 2(\beta -1)\cdot 354}$",G(1.75),NE);

     //attach(legend(),(point(S).x,truepoint(S).y),10S,UnFill);
  \end{asy}

RandomRatio1.tex
\begin{asy}
 defaultpen(fontsize(11));
 import graph;
 import gsl;
    // size(25cm,17cm,IgnoreAspect);
     size(15cm,10cm,IgnoreAspect);
     

     pen dashed=linetype(new real[] {4,4});
     pen p=linewidth(.75);
     pen p2=linewidth(3);

     //real g(real x) {return ((11/9*zeta(x)+29/36*(1/2+(1/((x-2)*(x-1))-1/(4*zeta(x-1)))/(zeta(x-1)^(x-1)*2^(x-1)))) / (zeta(x)+1/2+(1/((x-2)*(x-1))-1/(4*zeta(x-1)))/(zeta(x-1)^(x-1)*2^(x-1))));}
     real f(real x) {return ((11/9*zeta(x)+29/36*(1/2+(1/((x-2)*(x-1))-1/(4*zeta(x-1)))/(zeta(x-1)^(x-1)*2^(x-1))+(1/((x-1)*(x-2))/(2^(x*(x-1))*zeta(x-1)^(x-1))+1/zeta(x-1)^x*(1/2^(2x+1)-1/2^(2*x))))) / (zeta(x)+1/2+(1/((x-2)*(x-1))-1/(4*zeta(x-1)))/(zeta(x-1)^(x-1)*2^(x-1))+(1/((x-1)*(x-2))/(2^(x*(x-1))*zeta(x-1)^(x-1))+1/zeta(x-1)^x*(1/2^(2x+1)-1/2^(2*x)))));}
     pair F(real x) {return (x,f(x));}
     //real h(real x) {return ((11/9*zeta(x)+29/72)/(zeta(x)+1/2));}
     //pair H(real x) {return (x,h(x));}
     real j(real x) {return ((11/9*zeta(x)+145/144)/(zeta(x)+5/4));}
     pair J(real x) {return (x,j(x));}
     real k(real x) {return ((11/9*zeta(x)+145/288)/(zeta(x)+5/8));}
     //real k2(real x) {return ((11/9*zeta(x)+145/288)/(zeta(x)+5/8))-0.0001;}
     pair K(real x) {return (x,k(x));}
     //real l(real x) {return (8/7);}
  
     //draw("$g$",graph(g,2.01,5),dashed+p,"first analysis ($\rho$)");
     draw("",graph(f,2.01,3),p,"second analysis ($\rho'$)");
     //draw("$h$",graph(h,2.01,5),dotted+p,"second analysis ($\rho'$)");
//     draw("$\frac{8}{7}$",graph(l,1.5,3),dotted+p,"second analysis ($\rho'$)");
     draw("",graph(j,1.5,1.99),p,"second analysis ($\rho'$)");
     draw("",graph(k,2,2),p2,"second analysis ($\rho'$)");
     //draw("",graph(k2,1.999,2.001),p2,"second analysis ($\rho'$)");
     
    ylimits(j(1.99),1.11);
  //   xlimits(0,5);
     xaxis("$\beta$",BottomTop,LeftTicks);
     yaxis("expected approx. ratio",LeftRight,RightTicks);
     
     label("${a}(\beta)=\frac{\frac{11}{9}\zeta(2)+\frac{145}{288}}{\zeta(2)+\frac{5}{8}}$",(2,1.105),S);
     label("$\tilde{a}(\beta)=\frac{\frac{11}{9}\zeta(\beta)+\frac{145}{144}}{\zeta(\beta)+\frac{5}{4}}$",J(1.55),NE);
     label("$\hat{a}(\beta)=\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot E_k}{\zeta(\beta)+E_k}$",F(2.3),SE);


     //attach(legend(),(point(S).x,truepoint(S).y),10S,UnFill);
  \end{asy}
RandomRatio.tex
\begin{asy}
 defaultpen(fontsize(11));
 import graph;
 import gsl;
     size(15cm,10cm,IgnoreAspect);
     

     pen dashed=linetype(new real[] {4,4});
     pen p=linewidth(.75);

     //real e(real x) {return 8/7;}
     //real g(real x) {return ((11/9*zeta(x)+29/36*(1/2+(1/((x-2)*(x-1))-1/(4*zeta(x-1)))/(zeta(x-1)^(x-1)*2^(x-1)))) / (zeta(x)+1/2+(1/((x-2)*(x-1))-1/(4*zeta(x-1)))/(zeta(x-1)^(x-1)*2^(x-1))));}
     real f(real x) {return ((11/9*zeta(x)+29/36*(1/2+(1/((x-2)*(x-1))-1/(4*zeta(x-1)))/(zeta(x-1)^(x-1)*2^(x-1))+(1/((x-1)*(x-2))/(2^(x*(x-1))*zeta(x-1)^(x-1))+1/zeta(x-1)^x*(1/2^(2x+1)-1/2^(2*x))))) / (zeta(x)+1/2+(1/((x-2)*(x-1))-1/(4*zeta(x-1)))/(zeta(x-1)^(x-1)*2^(x-1))+(1/((x-1)*(x-2))/(2^(x*(x-1))*zeta(x-1)^(x-1))+1/zeta(x-1)^x*(1/2^(x^2+1)-1/2^(2*x)))));}
     pair F(real x) {return (x,f(x));}
     real h(real x) {return ((11/9*zeta(x)+29/72)/(zeta(x)+1/2));}
     pair H(real x) {return (x,h(x));}
  
     //draw("$8/7$",graph(e,2.1,7),dashed+p,"first analysis ($\rho$)");
     //draw("$g$",graph(g,2.1,7),dashed+p,"first analysis ($\rho$)");
     draw("",graph(f,2.1,7),p,"second analysis ($\rho'$)");
     draw("",graph(h,2.1,7),dashed+p,"second analysis ($\rho'$)");
     
 //    ylimits(1.968,2);
     xaxis("$\beta$",BottomTop,LeftTicks);
     yaxis("expected approx. ratio",LeftRight,RightTicks);
     
     label("$a(\beta)=\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{72}}{\zeta(\beta)+\frac{1}{2}}$",H(2.75),NE);
     label("$\hat{a}(\beta)=\frac{\frac{11}{9}\zeta(\beta)+\frac{29}{36}\cdot E_k}{\zeta(\beta)+E_k}$",F(2.3),SE);

     //attach(legend(),(point(S).x,truepoint(S).y),10S,UnFill);
  \end{asy}
TSPonPLG.tex
\documentclass[a4paper,12pt]{article}

% \documentclass[preprint,12pt]{elsarticle}

\input{mypreambel}

% \journal{Theoretical Computer Science}

\begin{document}

\title{\bf Approximability of TSP on Power Law Graphs\\[1ex]}
\author{Mikael Gast\thanks{Dept. of Computer Science and the Hausdorff Center for Mathematics, University of Bonn.
    e-mail:{ \texttt{\href{mailto:gast@cs.uni-bonn.de}{gast@cs.uni-bonn.de}}}} \and
	Mathias Hauptmann\thanks{Dept. of Computer Science, University of Bonn.
    e-mail:{ \texttt{\href{mailto:hauptman@cs.uni-bonn.de}{hauptman@cs.uni-bonn.de}}}} \and
	Marek Karpinski\thanks{Dept. of Computer Science and the Hausdorff Center for Mathematics, University of Bonn. Research supported by DFG grants and the Hausdorff grant EXC59-1.
    e-mail:{ \texttt{\href{mailto:marek@cs.uni-bonn.de}{marek@cs.uni-bonn.de}}}}}
%\author{Mikael Gast\thanks{Dept. of Computer Science, University of Bonn.
%    e-mail:{ \tt gast@cs.uni-bonn.de}} \and
%	Mathias Hauptmann\thanks{Dept. of Computer Science, University of Bonn.
%    e-mail:{ \tt hauptman@cs.uni-bonn.de}} \and
%	Marek Karpinski\thanks{Dept. of Computer Science, University of Bonn.
%    e-mail:{ \tt marek@cs.uni-bonn.de}}}
\date{}
\maketitle

\begin{abstract}
 In this paper we study the special case of Graphic TSP where the underlying graph is a \emph{power law graph} (PLG). We give a refined analysis of some of the current best approximation algorithms and show that an improved approximation ratio can be achieved for certain ranges of the \emph{power law exponent} $\beta$.
For the value of power law exponent $\beta=1.5$ we obtain an approximation ratio of $1.34$ for Graphic TSP. % and inapproximability bound of $1.0001$ for the Graphic TSP.
Moreover we study the $(1,2)$-TSP with the underlying graph of $1$-edges being a PLG. We show improved approximation ratios in the case of underlying deterministic PLGs for $\beta$ greater than $1.666$. %certain ranges of the power law exponent.
For underlying \emph{random} PLGs we further improve the analysis and show even better expected approximation ratio for the range of $\beta$ between $1$ and $3.5$. %$2<\beta<3.5$.
On the other hand we prove the first explicit inapproximability bounds for $(1,2)$-TSP for an underlying power law graph.
\end{abstract}

%\nocite{Gharan2011,Mucha2012,Blaeser2005,Sebo2014,Papadimitriou1993,Papadimitriou2006,Moemke2011,Lampis2012,
%Karpinski2013,Karpinski2013a,Karpinski2013b,Engebretsen2006,Berman2006,
%Christofides1976}

\input{Intro}
\input{Approx}
\input{Lower}

\newpage
\section{Further Research}
It remains an interesting open problem on improving our approximability results as well as their extension to other related cases.
It would be very interesting to shed some more light on the structural properties of the underlying problems.

\printbibliography

% \setlength{\bibsep}{1ex}
% \begin{small}
%  \input{VConPLG.bbl}

% \vspace*{3ex}
% \noindent\textbf{Bibliography}
% 
% \bibliographystyle{model1-num-names}
%  \bibliography{VConPLG.bib}
% \end{small}

\end{document}


TSPonPLG.bbl
% $ biblatex auxiliary file $
% $ biblatex version 1.7 $
% $ biber version 0.9.9 $
% Do not modify the above lines!
%
% This is an auxiliary file used by the 'biblatex' package.
% This file may safely be deleted. It will be recreated by
% biber or bibtex as required.
%
\begingroup
\makeatletter
\@ifundefined{ver@biblatex.sty}
  {\@latex@error
     {Missing 'biblatex' package}
     {The bibliography requires the 'biblatex' package.}
      \aftergroup\endinput}
  {}
\endgroup


\refsection{0}
  \entry{Aiello2001}{article}{}
    \name{labelname}{3}{}{%
      {{hash=4fea2121146a33bc8119b75691416d69}{Aiello}{A\bibinitperiod}{William}{W\bibinitperiod}{}{}{}{}}%
      {{hash=1d2495bc5132ebe0aba48b654d7adca3}{Chung}{C\bibinitperiod}{Fan}{F\bibinitperiod}{}{}{}{}}%
      {{hash=4c61c76e8ee84b26e87b8f0c01b1c553}{Lu}{L\bibinitperiod}{Linyuan}{L\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{3}{}{%
      {{hash=4fea2121146a33bc8119b75691416d69}{Aiello}{A\bibinitperiod}{William}{W\bibinitperiod}{}{}{}{}}%
      {{hash=1d2495bc5132ebe0aba48b654d7adca3}{Chung}{C\bibinitperiod}{Fan}{F\bibinitperiod}{}{}{}{}}%
      {{hash=4c61c76e8ee84b26e87b8f0c01b1c553}{Lu}{L\bibinitperiod}{Linyuan}{L\bibinitperiod}{}{}{}{}}%
    }
    \list{publisher}{1}{%
      {AK PETERS, LTD}%
    }
    \strng{namehash}{a6c71a1c2926f8d2c11c9b9886e7f1a6}
    \strng{fullhash}{a6c71a1c2926f8d2c11c9b9886e7f1a6}
    \field{labelalpha}{ACL01}
    \field{sortinit}{A}
    \field{abstract}{We propose a random graph model which is a special case of sparse random graphs with given degree sequences which satisfy a power law. This model involves only a small number of parameters, called log- size and log-log growth rate. These parameters capture some universal characteristics of massive graphs. Furthermore, from these parame- ters, various properties of the graph can be derived. For example, for certain ranges of the parameters, we will compute the expected distri- bution of the sizes of the connected components which almost surely occur with high probability. We will illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We will also discuss the threshold function, the giant component, and the evolution of random graphs in this model.}
    \field{issn}{1058-6458}
    \field{journaltitle}{Experimental Mathematics}
    \field{number}{1}
    \field{title}{{A random graph model for power law graphs}}
    \field{volume}{10}
    \field{year}{2001}
    \field{pages}{53\bibrangedash 66}
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Aiello, Chung, Lu/Aiello, Chung, Lu\_2001.pdf:pdf
    \endverb
  \endentry

  \entry{Taxonomy2015}{misc}{}
    \field{labelalpha}{AT15}
    \field{sortinit}{A}
    \field{shorthand}{AT15}
    \field{title}{{Approximation Taxonomy of Metric TSP}}
    \field{urlday}{25}
    \field{urlmonth}{08}
    \field{urlyear}{2015}
    \field{year}{2015}
    \verb{url}
    \verb http://theory.cs.uni-bonn.de/info5/tsp/
    \endverb
  \endentry

  \entry{Berman1999}{inproceedings}{}
    \name{labelname}{2}{}{%
      {{hash=994791de889032e5fa28581805545b2e}{Berman}{B\bibinitperiod}{Piotr}{P\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=994791de889032e5fa28581805545b2e}{Berman}{B\bibinitperiod}{Piotr}{P\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{editor}{3}{}{%
      {{hash=97e411b9f62bb4e2534fd233917caaae}{Wiedermann}{W\bibinitperiod}{Jiří}{J\bibinitperiod}{}{}{}{}}%
      {{hash=2fbd8f4aa6a3747ea0377eeef0512570}{{Emde\bibnamedelimb Boas}}{E\bibinitperiod}{Peter}{P\bibinitperiod}{}{}{}{}}%
      {{hash=3281cbf0581655dba2dcc4960e9b2bc2}{Nielsen}{N\bibinitperiod}{Mogens}{M\bibinitperiod}{}{}{}{}}%
    }
    \list{language}{1}{%
      {English}%
    }
    \list{publisher}{1}{%
      {Springer-Verlag}%
    }
    \strng{namehash}{eed3acc2b5a912a402c3c8e1ee21f62f}
    \strng{fullhash}{eed3acc2b5a912a402c3c8e1ee21f62f}
    \field{labelalpha}{BK99}
    \field{sortinit}{B}
    \field{abstract}{We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems like MAX-2SAT and E2-LIN-2, and the bounded degree graph problems, like MIS, Node Cover, and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold.}
    \field{booktitle}{Proceedings of the 26th international Conference on Automata, Languages and Programming}
    \field{isbn}{978-3-540-66224-2}
    \field{series}{ICALP '99}
    \field{title}{{On some tighter inapproximability results}}
    \field{volume}{1644}
    \field{year}{1999}
    \field{pages}{200\bibrangedash 209}
    \verb{doi}
    \verb 10.1007/3-540-48523-6\_17
    \endverb
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Berman, Karpinski/Berman, Karpinski\_1999.pdf:pdf
    \endverb
    \verb{url}
    \verb http://dx.doi.org/10.1007/3-540-48523-6\_17 http://www.springerlink.com/index/h16gqmq2cctlecmu.pdf
    \endverb
    \keyw{Approximation Algorithms,Approximation Hardness,Bounded Dependency Satisfiability,Breakpoint Graphs,Independent Set,MAX-CUT,Node Cover,Sorting by Reversals}
  \endentry

  \entry{Berman2001}{article}{}
    \name{labelname}{2}{}{%
      {{hash=994791de889032e5fa28581805545b2e}{Berman}{B\bibinitperiod}{Piotr}{P\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=994791de889032e5fa28581805545b2e}{Berman}{B\bibinitperiod}{Piotr}{P\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{eed3acc2b5a912a402c3c8e1ee21f62f}
    \strng{fullhash}{eed3acc2b5a912a402c3c8e1ee21f62f}
    \field{labelalpha}{BK01}
    \field{sortinit}{B}
    \field{journaltitle}{ECCC TR01-053}
    \field{title}{{Efficient amplifiers and bounded degree optimization}}
    \field{year}{2001}
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Berman, Karpinski/Berman, Karpinski\_2001.pdf:pdf
    \endverb
    \verb{url}
    \verb http://eccc.hpi-web.de/report/2001/053/download/
    \endverb
  \endentry

  \entry{Berman2006}{inproceedings}{}
    \name{labelname}{2}{}{%
      {{hash=994791de889032e5fa28581805545b2e}{Berman}{B\bibinitperiod}{Piotr}{P\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=994791de889032e5fa28581805545b2e}{Berman}{B\bibinitperiod}{Piotr}{P\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{eed3acc2b5a912a402c3c8e1ee21f62f}
    \strng{fullhash}{eed3acc2b5a912a402c3c8e1ee21f62f}
    \field{labelalpha}{BK06}
    \field{sortinit}{B}
    \field{booktitle}{Proceedings of the 17th annual ACM-SIAM Symposium on Discrete Algorithms}
    \field{isbn}{0-89871-605-5}
    \field{month}{01}
    \field{title}{{8/7-Approximation Algorithm for (1,2)-TSP}}
    \field{year}{2006}
    \field{pages}{641\bibrangedash 648}
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Berman, Karpinski/Berman, Karpinski\_2006.pdf:pdf
    \endverb
    \verb{url}
    \verb http://dl.acm.org/citation.cfm?id=1109557.1109627
    \endverb
  \endentry

  \entry{Blaeser2005}{inproceedings}{}
    \name{labelname}{2}{}{%
      {{hash=45ca409deec52a07e2f91f5e854a3c90}{Bläser}{B\bibinitperiod}{M.}{M\bibinitperiod}{}{}{}{}}%
      {{hash=3128530387f7a87640dd8d81fa9279de}{{Shankar\bibnamedelimb Ram}}{S\bibinitperiod}{L.}{L\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=45ca409deec52a07e2f91f5e854a3c90}{Bläser}{B\bibinitperiod}{M.}{M\bibinitperiod}{}{}{}{}}%
      {{hash=3128530387f7a87640dd8d81fa9279de}{{Shankar\bibnamedelimb Ram}}{S\bibinitperiod}{L.}{L\bibinitperiod}{}{}{}{}}%
    }
    \list{publisher}{1}{%
      {Springer}%
    }
    \strng{namehash}{1055479ffa45f1814390c164ddb429b0}
    \strng{fullhash}{1055479ffa45f1814390c164ddb429b0}
    \field{labelalpha}{BSR05}
    \field{sortinit}{B}
    \field{abstract}{The minimum traveling salesman problem with distances one and two is the following problem: Given a complete undirected graph G = (V, E) with a cost function w: E → \{1, 2\}, find a Hamiltonian tour of minimum cost. In this paper, we provide an approximation algorithm for this problem achieving a performance guarantee of 315 271. This algorithm can be further improved obtaining a performance guarantee of 65 56. This is better than the one achieved by Papadimitriou and Yannakakis [8], with a ratio 7 6, more than a decade ago. We enhance their algorithm by an involved procedure and find an improved lower bound for the cost of an optimal Hamiltonian tour.}
    \field{booktitle}{Proceedings of the 15th International Symposium on Fundamentals of Computation Theory}
    \field{isbn}{3-540-28193-2}
    \field{issn}{0302-9743}
    \field{series}{FCT '05}
    \field{title}{{An improved approximation algorithm for TSP with distances one and two}}
    \field{volume}{LNCS 3623}
    \field{year}{2005}
    \field{pages}{504\bibrangedash 515}
    \verb{url}
    \verb http://cat.inist.fr/?aModele=afficheN\&cpsidt=17115578
    \endverb
    \keyw{Algorithme approximation,Algoritmo aproximación,Approximation algorithm,Borne inférieure,Complete graph,Computer theory,Cota inferior,Grafo completo,Grafo no orientado,Graphe complet,Graphe non orienté,Hamiltonian,Hamiltonian mechanics,Hamiltoniano,Hamiltonien,Informatique théorique,Informática teórica,Lower bound,Mecánica hamiltoniana,Mécanique hamiltonienne,Non directed graph,Problema viajante comercio,Problème commis voyageur,Travelling salesman problem}
  \endentry

  \entry{Christofides1976}{report}{}
    \name{labelname}{1}{}{%
      {{hash=b9677598d203ef2d59db8effb9d58ced}{Christofides}{C\bibinitperiod}{Nicos}{N\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=b9677598d203ef2d59db8effb9d58ced}{Christofides}{C\bibinitperiod}{Nicos}{N\bibinitperiod}{}{}{}{}}%
    }
    \list{institution}{1}{%
      {CS-93-13, Carnegie-Mellon University, Pittsburgh}%
    }
    \strng{namehash}{b9677598d203ef2d59db8effb9d58ced}
    \strng{fullhash}{b9677598d203ef2d59db8effb9d58ced}
    \field{labelalpha}{Chr76}
    \field{sortinit}{C}
    \field{title}{{Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem}}
    \field{type}{techreport}
    \field{year}{1976}
    \verb{url}
    \verb http://oai.dtic.mil/oai/oai?verb=getRecord\&metadataPrefix=html\&identifier=ADA025602
    \endverb
  \endentry

  \entry{Engebretsen2003}{article}{}
    \name{labelname}{1}{}{%
      {{hash=33caaa88307395370b838c7a66ca4152}{Engebretsen}{E\bibinitperiod}{Lars}{L\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=33caaa88307395370b838c7a66ca4152}{Engebretsen}{E\bibinitperiod}{Lars}{L\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{33caaa88307395370b838c7a66ca4152}
    \strng{fullhash}{33caaa88307395370b838c7a66ca4152}
    \field{labelalpha}{Eng03}
    \field{sortinit}{E}
    \field{issn}{0178-4617}
    \field{journaltitle}{Algorithmica}
    \field{month}{04}
    \field{number}{4}
    \field{title}{{An Explicit Lower Bound for TSP with Distances One and Two}}
    \field{volume}{35}
    \field{year}{2003}
    \field{pages}{301\bibrangedash 319}
    \verb{doi}
    \verb 10.1007/s00453-002-1001-6
    \endverb
    \verb{url}
    \verb http://link.springer.com/10.1007/s00453-002-1001-6
    \endverb
  \endentry

  \entry{Engebretsen2006}{article}{}
    \name{labelname}{2}{}{%
      {{hash=33caaa88307395370b838c7a66ca4152}{Engebretsen}{E\bibinitperiod}{Lars}{L\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=33caaa88307395370b838c7a66ca4152}{Engebretsen}{E\bibinitperiod}{Lars}{L\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{3b0b78ce587240b6f5bc8ea455c93af7}
    \strng{fullhash}{3b0b78ce587240b6f5bc8ea455c93af7}
    \field{labelalpha}{EK06}
    \field{sortinit}{E}
    \field{abstract}{The general asymmetric TSP with triangle inequality is known to be approximable only within logarithmic factors. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics, i.e., metrics where the distances are integers between one and some constant upper bound. In this case, the problem is known to be approximable within a constant factor. We prove that it is NP-hard to approximate the asymmetric TSP with distances one and two within 321/320−$\epsilon$ and that it is NP-hard to approximate the symmetric TSP with distances one and two within 741/740−$\epsilon$ for every constant $\epsilon$>0. Recently, Papadimitriou and Vempala announced improved approximation hardness results for both symmetric and asymmetric TSP with graph metric. We show that a similar construction can be used to obtain only slightly weaker approximation hardness results for TSP with triangle inequality and distances that are integers between one and eight. This shows that the Papadimitriou–Vempala construction is “local” in nature and, intuitively, indicates that it cannot be used to obtain hardness factors that grow with the size of the instance.}
    \field{issn}{00220000}
    \field{journaltitle}{Journal of Computer and System Sciences}
    \field{month}{06}
    \field{number}{4}
    \field{title}{{TSP with Bounded Metrics}}
    \field{volume}{72}
    \field{year}{2006}
    \field{pages}{509\bibrangedash 546}
    \verb{doi}
    \verb 10.1016/j.jcss.2005.12.001
    \endverb
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Engebretsen, Karpinski/Engebretsen, Karpinski\_2006.pdf:pdf
    \endverb
    \verb{url}
    \verb http://www.sciencedirect.com/science/article/pii/S0022000005001285
    \endverb
    \keyw{Approximation hardness,Bounded metric,Metric TSP}
  \endentry

  \entry{Gast2015}{article}{}
    \name{labelname}{3}{}{%
      {{hash=14eef464a2be63b1783f72d98551edf2}{Gast}{G\bibinitperiod}{Mikael}{M\bibinitperiod}{}{}{}{}}%
      {{hash=dd9cae92720dcc1ea32d6cb13b4a8eef}{Hauptmann}{H\bibinitperiod}{Mathias}{M\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{3}{}{%
      {{hash=14eef464a2be63b1783f72d98551edf2}{Gast}{G\bibinitperiod}{Mikael}{M\bibinitperiod}{}{}{}{}}%
      {{hash=dd9cae92720dcc1ea32d6cb13b4a8eef}{Hauptmann}{H\bibinitperiod}{Mathias}{M\bibinitperiod}{}{}{}{}}%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{2c6bff04d2c76816e72df46810109fc9}
    \strng{fullhash}{2c6bff04d2c76816e72df46810109fc9}
    \field{labelalpha}{GHK15}
    \field{sortinit}{G}
    \field{abstract}{We prove the first logarithmic lower bounds for the approximability of the Minimum Dominating Set problem for the case of connected ($\alpha$,$\beta$)-power law graphs for $\alpha$ being a size parameter and $\beta$ the power law exponent. We give also a best up to now upper approximation bound for this problem in the case of the parameters $\beta$>2. We develop also a new functional method for proving lower approximation bounds and display a sharp approximation phase transition area between approximability and inapproximability of the underlying problems. Our results depend on a method which could be also of independent interest.}
    \field{issn}{03043975}
    \field{journaltitle}{Theoretical Computer Science}
    \field{month}{01}
    \field{title}{{Inapproximability of dominating set on power law graphs}}
    \field{volume}{562}
    \field{year}{2015}
    \field{pages}{436\bibrangedash 452}
    \verb{doi}
    \verb 10.1016/j.tcs.2014.10.021
    \endverb
    \verb{url}
    \verb http://www.sciencedirect.com/science/article/pii/S030439751400783X
    \endverb
    \keyw{Approximation algorithms,Combinatorial optimization,Dominating set,Inapproximability,Power law graphs}
  \endentry

  \entry{Gharan2011}{inproceedings}{}
    \name{labelname}{3}{}{%
      {{hash=a6a7dffa6588cbb9efde54544a60dc7f}{Gharan}{G\bibinitperiod}{Shayan\bibnamedelima Oveis}{S\bibinitperiod\bibinitdelim O\bibinitperiod}{}{}{}{}}%
      {{hash=c1ff07445a1f57599a7367625b7ae304}{Saberi}{S\bibinitperiod}{Amin}{A\bibinitperiod}{}{}{}{}}%
      {{hash=9e03a993926cad4dd9bd1244c29d9f9a}{Singh}{S\bibinitperiod}{Mohit}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{3}{}{%
      {{hash=a6a7dffa6588cbb9efde54544a60dc7f}{Gharan}{G\bibinitperiod}{Shayan\bibnamedelima Oveis}{S\bibinitperiod\bibinitdelim O\bibinitperiod}{}{}{}{}}%
      {{hash=c1ff07445a1f57599a7367625b7ae304}{Saberi}{S\bibinitperiod}{Amin}{A\bibinitperiod}{}{}{}{}}%
      {{hash=9e03a993926cad4dd9bd1244c29d9f9a}{Singh}{S\bibinitperiod}{Mohit}{M\bibinitperiod}{}{}{}{}}%
    }
    \list{language}{1}{%
      {English}%
    }
    \list{publisher}{1}{%
      {IEEE}%
    }
    \strng{namehash}{601da9dbd52918a27356d6676c5ec704}
    \strng{fullhash}{601da9dbd52918a27356d6676c5ec704}
    \field{labelalpha}{GSS11}
    \field{sortinit}{G}
    \field{booktitle}{Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science}
    \field{isbn}{978-0-7695-4571-4}
    \field{issn}{0272-5428}
    \field{month}{10}
    \field{series}{FOCS}
    \field{title}{{A Randomized Rounding Approach to the Traveling Salesman Problem}}
    \field{year}{2011}
    \field{pages}{550\bibrangedash 559}
    \verb{doi}
    \verb 10.1109/FOCS.2011.80
    \endverb
    \verb{url}
    \verb http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6108216
    \endverb
    \keyw{Algorithm design and analysis,Approximation Algorithms,Approximation algorithms,Approximation methods,Educational institutions,Entropy,Eulerian augmentation,Measurement,Random Spanning Trees,Randomized Rounding,Rayleigh measurement,Traveling Salesman Problem,Traveling salesman problems,approximation algorithm,graph theory,linear programming,polyhedral theory,positive constant,probability,probability theory,randomized rounding approach,spanning tree,traveling salesman problem,travelling salesman problems}
  \endentry

  \entry{Hartvigsen1984}{thesis}{}
    \name{labelname}{1}{}{%
      {{hash=34a6cab59d01071b11b091819e5ff345}{Hartvigsen}{H\bibinitperiod}{D.\bibnamedelimi B.}{D\bibinitperiod\bibinitdelim B\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=34a6cab59d01071b11b091819e5ff345}{Hartvigsen}{H\bibinitperiod}{D.\bibnamedelimi B.}{D\bibinitperiod\bibinitdelim B\bibinitperiod}{}{}{}{}}%
    }
    \list{institution}{1}{%
      {Carnegie-Mellon University}%
    }
    \strng{namehash}{34a6cab59d01071b11b091819e5ff345}
    \strng{fullhash}{34a6cab59d01071b11b091819e5ff345}
    \field{labelalpha}{Har84}
    \field{sortinit}{H}
    \field{title}{{Extensions of matching theory}}
    \field{type}{phdthesis}
    \field{year}{1984}
  \endentry

  \entry{Hastad2001}{article}{}
    \name{labelname}{1}{}{%
      {{hash=804cd45ec4be77b4cc5e4d994ba18af0}{Håstad}{H\bibinitperiod}{Johan}{J\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=804cd45ec4be77b4cc5e4d994ba18af0}{Håstad}{H\bibinitperiod}{Johan}{J\bibinitperiod}{}{}{}{}}%
    }
    \list{publisher}{1}{%
      {ACM}%
    }
    \strng{namehash}{804cd45ec4be77b4cc5e4d994ba18af0}
    \strng{fullhash}{804cd45ec4be77b4cc5e4d994ba18af0}
    \field{labelalpha}{Hås01}
    \field{sortinit}{H}
    \field{issn}{00045411}
    \field{journaltitle}{Journal of the ACM}
    \field{month}{07}
    \field{number}{4}
    \field{title}{{Some optimal inapproximability results}}
    \field{volume}{48}
    \field{year}{2001}
    \field{pages}{798\bibrangedash 859}
    \verb{doi}
    \verb 10.1145/502090.502098
    \endverb
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Håstad/Håstad\_2001.pdf:pdf
    \endverb
    \verb{url}
    \verb http://dl.acm.org/citation.cfm?id=502090.502098
    \endverb
    \keyw{Inapproximability,NP-hard optimization problems,linear equations,max-sat,probabilistically checkable proofs}
  \endentry

  \entry{Karpinski2015}{incollection}{}
    \name{labelname}{1}{}{%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{5482fd910692daec95489dd87da34892}
    \strng{fullhash}{5482fd910692daec95489dd87da34892}
    \field{labelalpha}{Kar15}
    \field{sortinit}{K}
    \field{abstract}{We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the underlying paradigms and insights which lead to the recent improvements as well as some inherent obstacles for further progress on those problems.}
    \field{booktitle}{Proceedings of the 20th International Symposium on Fundamentals of Computation Theory}
    \field{title}{{Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies}}
    \field{volume}{LNCS 9210}
    \field{year}{2015}
    \field{pages}{3\bibrangedash 11}
    \verb{doi}
    \verb 10.1007/978-3-319-22177-9\_1
    \endverb
    \verb{url}
    \verb http://link.springer.com/10.1007/978-3-319-22177-9\_1
    \endverb
  \endentry

  \entry{Karpinski2013}{inproceedings}{}
    \name{labelname}{3}{}{%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
      {{hash=40ca71239d2314998ff8ba183452d8b8}{Lampis}{L\bibinitperiod}{Michael}{M\bibinitperiod}{}{}{}{}}%
      {{hash=08f75fa885f19b4be8f8d9bca4ca423d}{Schmied}{S\bibinitperiod}{Richard}{R\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{3}{}{%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
      {{hash=40ca71239d2314998ff8ba183452d8b8}{Lampis}{L\bibinitperiod}{Michael}{M\bibinitperiod}{}{}{}{}}%
      {{hash=08f75fa885f19b4be8f8d9bca4ca423d}{Schmied}{S\bibinitperiod}{Richard}{R\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{cb34272b752483a461925035bb5a303d}
    \strng{fullhash}{cb34272b752483a461925035bb5a303d}
    \field{labelalpha}{KLS13}
    \field{sortinit}{K}
    \field{abstract}{In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.}
    \field{booktitle}{Algorithms and Computation}
    \field{series}{Lecture Notes in Computer Science}
    \field{title}{{New Inapproximability Bounds for TSP}}
    \field{volume}{8283}
    \field{year}{2013}
    \field{pages}{568\bibrangedash 578}
    \verb{doi}
    \verb 10.1007/978-3-642-45030-3\_53
    \endverb
    \verb{url}
    \verb http://link.springer.com/content/pdf/10.1007/978-3-642-45030-3.pdf\#page=583 http://link.springer.com/10.1007/978-3-642-45030-3\_53
    \endverb
  \endentry

  \entry{Karpinski2013b}{article}{}
    \name{labelname}{2}{}{%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
      {{hash=08f75fa885f19b4be8f8d9bca4ca423d}{Schmied}{S\bibinitperiod}{Richard}{R\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
      {{hash=08f75fa885f19b4be8f8d9bca4ca423d}{Schmied}{S\bibinitperiod}{Richard}{R\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{85a5676cbb31e813e7f58761b7c16406}
    \strng{fullhash}{85a5676cbb31e813e7f58761b7c16406}
    \field{labelalpha}{KS13}
    \field{sortinit}{K}
    \field{extraalpha}{1}
    \field{abstract}{We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used in the paper could be also of independent interest.}
    \field{eprinttype}{arXiv}
    \field{journaltitle}{arXiv preprint arXiv:1304.6800}
    \field{month}{04}
    \field{title}{{Approximation Hardness of Graphic TSP on Cubic Graphs}}
    \field{year}{2013}
    \field{pages}{19}
    \verb{eprint}
    \verb 1304.6800
    \endverb
    \verb{url}
    \verb http://arxiv.org/abs/1304.6800
    \endverb
  \endentry

  \entry{Karpinski2013a}{inproceedings}{}
    \name{labelname}{2}{}{%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
      {{hash=08f75fa885f19b4be8f8d9bca4ca423d}{Schmied}{S\bibinitperiod}{Richard}{R\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=5482fd910692daec95489dd87da34892}{Karpinski}{K\bibinitperiod}{Marek}{M\bibinitperiod}{}{}{}{}}%
      {{hash=08f75fa885f19b4be8f8d9bca4ca423d}{Schmied}{S\bibinitperiod}{Richard}{R\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{85a5676cbb31e813e7f58761b7c16406}
    \strng{fullhash}{85a5676cbb31e813e7f58761b7c16406}
    \field{labelalpha}{KS13}
    \field{sortinit}{K}
    \field{extraalpha}{2}
    \field{booktitle}{Proceedings of the 19th Computing: The Australasian Theory Symposium, CRPIT 141}
    \field{isbn}{978-1-921770-26-5}
    \field{month}{01}
    \field{title}{{Improved Inapproximability Results for the Shortest Superstring and Related Problems}}
    \field{year}{2013}
    \field{pages}{27\bibrangedash 36}
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Karpinski, Schmied/Karpinski, Schmied\_2013.pdf:pdf
    \endverb
    \verb{url}
    \verb http://dl.acm.org/citation.cfm?id=2525519.2525523
    \endverb
    \keyw{MAX-ATSP problem,asymmetric traveling salesperson problem,bounded metrics,explicit lower bounds,inapproximability,maximum compression problem,shortest superstring problem}
  \endentry

  \entry{Karp1972}{article}{}
    \name{labelname}{1}{}{%
      {{hash=5d77d3cf25d2ee3ce64732bb77de0b0f}{Karp}{K\bibinitperiod}{Richard\bibnamedelima M.}{R\bibinitperiod\bibinitdelim M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=5d77d3cf25d2ee3ce64732bb77de0b0f}{Karp}{K\bibinitperiod}{Richard\bibnamedelima M.}{R\bibinitperiod\bibinitdelim M\bibinitperiod}{}{}{}{}}%
    }
    \name{editor}{2}{}{%
      {{hash=a429a8a3692d75672f26c2fc74e92546}{Miller}{M\bibinitperiod}{R\bibnamedelima E}{R\bibinitperiod\bibinitdelim E\bibinitperiod}{}{}{}{}}%
      {{hash=9f02f9a41ec80dadfe0b0fc96a3988c5}{Thatcher}{T\bibinitperiod}{J\bibnamedelima W}{J\bibinitperiod\bibinitdelim W\bibinitperiod}{}{}{}{}}%
    }
    \list{institution}{1}{%
      {University of California at Berkeley}%
    }
    \list{publisher}{1}{%
      {Springer}%
    }
    \strng{namehash}{5d77d3cf25d2ee3ce64732bb77de0b0f}
    \strng{fullhash}{5d77d3cf25d2ee3ce64732bb77de0b0f}
    \field{labelalpha}{Kar72}
    \field{sortinit}{K}
    \field{abstract}{A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains. Through simple encodings from such domains into the set of words over a finite alphabet these problems can be converted into language recognition problems, and we can inquire into their computational complexity. It is reasonable to consider such a problem satisfactorily solved when an algorithm for its solution is found which terminates within a number of steps bounded by a polynomial in the length of the input. We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent, in the sense that either each of them possesses a polynomial-bounded algorithm or none of them does.}
    \field{isbn}{0306307073}
    \field{issn}{00224812}
    \field{journaltitle}{Complexity of Computer Computations}
    \field{month}{12}
    \field{title}{{Reducibility among combinatorial problems}}
    \field{year}{1972}
    \field{pages}{85\bibrangedash 103}
    \verb{doi}
    \verb 10.2307/2271828
    \endverb
    \verb{url}
    \verb http://www.springerlink.com/index/L45H7011865P0257.pdf http://www.jstor.org/stable/2271828?origin=crossref
    \endverb
  \endentry

  \entry{Lampis2012}{incollection}{}
    \name{labelname}{1}{}{%
      {{hash=40ca71239d2314998ff8ba183452d8b8}{Lampis}{L\bibinitperiod}{Michael}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=40ca71239d2314998ff8ba183452d8b8}{Lampis}{L\bibinitperiod}{Michael}{M\bibinitperiod}{}{}{}{}}%
    }
    \list{publisher}{1}{%
      {Springer Berlin Heidelberg}%
    }
    \strng{namehash}{40ca71239d2314998ff8ba183452d8b8}
    \strng{fullhash}{40ca71239d2314998ff8ba183452d8b8}
    \field{labelalpha}{Lam12}
    \field{sortinit}{L}
    \field{abstract}{The Traveling Salesman Problem is one of the most studied problems in computational complexity and its approximability has been a long standing open question. Currently, the best known inapproximability threshold known is 220/219 due to Papadimitriou and Vempala. Here, using an essentially different construction and also relying on the work of Berman and Karpinski on bounded occurrence CSPs, we give an alternative and simpler inapproximability proof which improves the bound to 185/184.}
    \field{booktitle}{Proceedings 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012}
    \field{series}{Lecture Notes in Computer Science}
    \field{title}{{Improved Inapproximability for TSP}}
    \field{volume}{7408}
    \field{year}{2012}
    \field{pages}{243\bibrangedash 253}
    \verb{doi}
    \verb 10.1007/978-3-642-32512-0\_21
    \endverb
    \verb{url}
    \verb http://link.springer.com/10.1007/978-3-642-32512-0\_21
    \endverb
  \endentry

  \entry{Manthey2008}{article}{}
    \name{labelname}{1}{}{%
      {{hash=a372d2667d341069934dd1c5d64e2e1c}{Manthey}{M\bibinitperiod}{Bodo}{B\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=a372d2667d341069934dd1c5d64e2e1c}{Manthey}{M\bibinitperiod}{Bodo}{B\bibinitperiod}{}{}{}{}}%
    }
    \list{language}{1}{%
      {en}%
    }
    \list{publisher}{2}{%
      {Society for Industrial}%
      {Applied Mathematics}%
    }
    \strng{namehash}{a372d2667d341069934dd1c5d64e2e1c}
    \strng{fullhash}{a372d2667d341069934dd1c5d64e2e1c}
    \field{labelalpha}{Man08}
    \field{sortinit}{M}
    \field{abstract}{A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges. We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that, for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is \$\backslash mathsf\{APX\}\$-hard. Most of our hardness results hold even if the edge weights are restricted to zero and one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated within a factor of 2 for undirected graphs and within a factor of \$8/3\$ in the case of directed graphs. This holds for arbitrary sets L.}
    \field{issn}{0097-5397}
    \field{journaltitle}{SIAM Journal on Computing}
    \field{month}{01}
    \field{number}{1}
    \field{title}{{On Approximating Restricted Cycle Covers}}
    \field{volume}{38}
    \field{year}{2008}
    \field{pages}{181\bibrangedash 206}
    \verb{doi}
    \verb 10.1137/060676003
    \endverb
    \verb{url}
    \verb http://epubs.siam.org/doi/abs/10.1137/060676003
    \endverb
    \keyw{68Q17,68Q25,68R10,68W25,90C27,approximation algorithms,cycle covers,inapproximability,two-factors}
  \endentry

  \entry{Moemke2011}{inproceedings}{}
    \name{labelname}{2}{}{%
      {{hash=daaf0b323c101aa774d5efa4d7311557}{Mömke}{M\bibinitperiod}{Tobias}{T\bibinitperiod}{}{}{}{}}%
      {{hash=a8121723fec40d2bb3f1a992ccf73f9f}{Svensson}{S\bibinitperiod}{Ola}{O\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=daaf0b323c101aa774d5efa4d7311557}{Mömke}{M\bibinitperiod}{Tobias}{T\bibinitperiod}{}{}{}{}}%
      {{hash=a8121723fec40d2bb3f1a992ccf73f9f}{Svensson}{S\bibinitperiod}{Ola}{O\bibinitperiod}{}{}{}{}}%
    }
    \list{publisher}{1}{%
      {IEEE}%
    }
    \strng{namehash}{c356fe7144652cb1e0ec9ef2c71e3542}
    \strng{fullhash}{c356fe7144652cb1e0ec9ef2c71e3542}
    \field{labelalpha}{MS11}
    \field{sortinit}{M}
    \field{abstract}{We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.}
    \field{booktitle}{Proceedings 52nd IEEE Annual Symposium on Foundations of Computer Science}
    \field{isbn}{978-0-7695-4571-4}
    \field{issn}{0272-5428}
    \field{month}{10}
    \field{shorttitle}{Foundations of Computer Science (FOCS), 2011 IEEE}
    \field{title}{{Approximating Graphic TSP by Matchings}}
    \field{year}{2011}
    \field{pages}{560\bibrangedash 569}
    \verb{doi}
    \verb 10.1109/FOCS.2011.56
    \endverb
    \verb{url}
    \verb http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6108217
    \endverb
    \keyw{Algorithm design and analysis,Approximation algorithms,Approximation methods,Graphics,Held-Karp lower bound,Held-Karp relaxation matches,Measurement,Polynomials,TSP,Traveling salesman problems,approximation,approximation algorithm,approximation theory,graph theory,graphic TSP,graphic metrics,linear programming,traveling salesman path problem,travelling salesman problems}
  \endentry

  \entry{Mucha2012}{article}{}
    \name{labelname}{1}{}{%
      {{hash=ada4c082d38595a3273371a5154ec423}{Mucha}{M\bibinitperiod}{Marcin}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{1}{}{%
      {{hash=ada4c082d38595a3273371a5154ec423}{Mucha}{M\bibinitperiod}{Marcin}{M\bibinitperiod}{}{}{}{}}%
    }
    \strng{namehash}{ada4c082d38595a3273371a5154ec423}
    \strng{fullhash}{ada4c082d38595a3273371a5154ec423}
    \field{labelalpha}{Muc12}
    \field{sortinit}{M}
    \field{issn}{1432-4350}
    \field{journaltitle}{Theory of Computing Systems}
    \field{month}{12}
    \field{number}{4}
    \field{title}{{13/9-Approximation for Graphic TSP}}
    \field{volume}{55}
    \field{year}{2012}
    \field{pages}{640\bibrangedash 657}
    \verb{doi}
    \verb 10.1007/s00224-012-9439-7
    \endverb
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Mucha/Mucha\_2012.pdf:pdf
    \endverb
    \verb{url}
    \verb http://link.springer.com/10.1007/s00224-012-9439-7
    \endverb
  \endentry

  \entry{Papadimitriou1993}{article}{}
    \name{labelname}{2}{}{%
      {{hash=e8e90b2073ea781d4957f8e607cf44f7}{Papadimitriou}{P\bibinitperiod}{Christos\bibnamedelima H.}{C\bibinitperiod\bibinitdelim H\bibinitperiod}{}{}{}{}}%
      {{hash=4c46d2f3f797a5dedce8a376cb13fe3a}{Yannakakis}{Y\bibinitperiod}{Mihalis}{M\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=e8e90b2073ea781d4957f8e607cf44f7}{Papadimitriou}{P\bibinitperiod}{Christos\bibnamedelima H.}{C\bibinitperiod\bibinitdelim H\bibinitperiod}{}{}{}{}}%
      {{hash=4c46d2f3f797a5dedce8a376cb13fe3a}{Yannakakis}{Y\bibinitperiod}{Mihalis}{M\bibinitperiod}{}{}{}{}}%
    }
    \list{language}{1}{%
      {en}%
    }
    \list{publisher}{1}{%
      {INFORMS}%
    }
    \strng{namehash}{e8ec12240bea4f213bf94b8491822003}
    \strng{fullhash}{e8ec12240bea4f213bf94b8491822003}
    \field{labelalpha}{PY93}
    \field{sortinit}{P}
    \field{abstract}{We present a polynomial-time approximation algorithm with worst-case ratio 7/6 for the special case of the traveling salesman problem in which all distances are either one or two. We also show that this special case of the traveling salesman problem is MAX SNP-hard, and therefore it is unlikely that it has a polynomial-time approximation scheme.}
    \field{issn}{0364-765X}
    \field{journaltitle}{Mathematics of Operations Research}
    \field{month}{02}
    \field{number}{1}
    \field{title}{{The Traveling Salesman Problem with Distances One and Two}}
    \field{volume}{18}
    \field{year}{1993}
    \field{pages}{1\bibrangedash 11}
    \verb{doi}
    \verb 10.1287/moor.18.1.1
    \endverb
    \verb{url}
    \verb http://pubsonline.informs.org/doi/abs/10.1287/moor.18.1.1
    \endverb
    \keyw{computational complexity,polynomial-time algorithms,traveling salesman}
  \endentry

  \entry{Sahni1976}{article}{}
    \name{labelname}{2}{}{%
      {{hash=7e90325f25f41d005a9a47e28fd30bf0}{Sahni}{S\bibinitperiod}{Sartaj}{S\bibinitperiod}{}{}{}{}}%
      {{hash=920f6578893cb2e7b8ac997178968f27}{Gonzalez}{G\bibinitperiod}{Teofilo}{T\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=7e90325f25f41d005a9a47e28fd30bf0}{Sahni}{S\bibinitperiod}{Sartaj}{S\bibinitperiod}{}{}{}{}}%
      {{hash=920f6578893cb2e7b8ac997178968f27}{Gonzalez}{G\bibinitperiod}{Teofilo}{T\bibinitperiod}{}{}{}{}}%
    }
    \list{publisher}{1}{%
      {ACM}%
    }
    \strng{namehash}{cf0569040a92efdccd530197b2b4f7c8}
    \strng{fullhash}{cf0569040a92efdccd530197b2b4f7c8}
    \field{labelalpha}{SG76}
    \field{sortinit}{S}
    \field{issn}{00045411}
    \field{journaltitle}{Journal of the ACM}
    \field{month}{07}
    \field{number}{3}
    \field{title}{{P-Complete Approximation Problems}}
    \field{volume}{23}
    \field{year}{1976}
    \field{pages}{555\bibrangedash 565}
    \verb{doi}
    \verb 10.1145/321958.321975
    \endverb
    \verb{file}
    \verb :home/mikael/Dropbox/Public/Mendeley/Sahni, Gonzalez/Sahni, Gonzalez\_1976.pdf:pdf
    \endverb
    \verb{url}
    \verb http://dl.acm.org/citation.cfm?id=321958.321975
    \endverb
  \endentry

  \entry{Sebo2014}{article}{}
    \name{labelname}{2}{}{%
      {{hash=e5fe6b97b41dd05607dc1ddbd400ace1}{Sebő}{S\bibinitperiod}{András}{A\bibinitperiod}{}{}{}{}}%
      {{hash=60b91c18a457236628f65ee35ab35ddb}{Vygen}{V\bibinitperiod}{Jens}{J\bibinitperiod}{}{}{}{}}%
    }
    \name{author}{2}{}{%
      {{hash=e5fe6b97b41dd05607dc1ddbd400ace1}{Sebő}{S\bibinitperiod}{András}{A\bibinitperiod}{}{}{}{}}%
      {{hash=60b91c18a457236628f65ee35ab35ddb}{Vygen}{V\bibinitperiod}{Jens}{J\bibinitperiod}{}{}{}{}}%
    }
    \list{publisher}{1}{%
      {Springer-Verlag New York, Inc.}%
    }
    \strng{namehash}{e88f2283af6ac260c6c2910a1daccbb7}
    \strng{fullhash}{e88f2283af6ac260c6c2910a1daccbb7}
    \field{labelalpha}{SV14}
    \field{sortinit}{S}
    \field{issn}{0209-9683}
    \field{journaltitle}{Combinatorica}
    \field{month}{11}
    \field{number}{5}
    \field{title}{{Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs}}
    \field{volume}{34}
    \field{year}{2014}
    \field{pages}{597\bibrangedash 629}
    \verb{doi}
    \verb 10.1007/s00493-014-2960-3
    \endverb
    \verb{url}
    \verb http://dl.acm.org/citation.cfm?id=2688265.2688281
    \endverb
    \keyw{05C85,68R10,90C27}
  \endentry

  \lossort
    \key{Taxonomy2015}
  \endlossort

\endrefsection
\endinput

