  We analyze two classic variants of the Traveling Salesman Problem using the
toolkit of fine-grained complexity. Our first set of results is motivated by
the Bitonic TSP problem: given a set of $n$ points in the plane, compute a
shortest tour consisting of two monotone chains. It is a classic
dynamic-programming exercise to solve this problem in $O(n^2)$ time. While the
near-quadratic dependency of similar dynamic programs for Longest Common
Subsequence and Discrete Frechet Distance has recently been proven to be
essentially optimal under the Strong Exponential Time Hypothesis, we show that
bitonic tours can be found in subquadratic time. More precisely, we present an
algorithm that solves bitonic TSP in $O(n \log^2 n)$ time and its bottleneck
version in $O(n \log^3 n)$ time. Our second set of results concerns the popular
$k$-OPT heuristic for TSP in the graph setting. More precisely, we study the
$k$-OPT decision problem, which asks whether a given tour can be improved by a
$k$-OPT move that replaces $k$ edges in the tour by $k$ new edges. A simple
algorithm solves $k$-OPT in $O(n^k)$ time for fixed $k$. For 2-OPT, this is
easily seen to be optimal. For $k=3$ we prove that an algorithm with a runtime
of the form $\tilde{O}(n^{3-\epsilon})$ exists if and only if All-Pairs
Shortest Paths in weighted digraphs has such an algorithm. The results for
$k=2,3$ may suggest that the actual time complexity of $k$-OPT is
$\Theta(n^k)$. We show that this is not the case, by presenting an algorithm
that finds the best $k$-move in $O(n^{\lfloor 2k/3 \rfloor + 1})$ time for
fixed $k \geq 3$. This implies that 4-OPT can be solved in $O(n^3)$ time,
matching the best-known algorithm for 3-OPT. Finally, we show how to beat the
quadratic barrier for $k=2$ in two important settings, namely for points in the
plane and when we want to solve 2-OPT repeatedly.
