[Math] Proving a lower bound for the traveling salesman problem

graph theory

This link provides a guide for bounding solutions to the traveling salesman problem (TSP). In it, the author gives a lower bound on the optimal cost of any tour. For each vertex $v$ in the problem:

$$\text{cost of any tour} >= \frac{1}{2}\sum_{v\in V}\text{(sum of each $v$'s two least cost edges)}$$

(by the way, I'm not sure if there's better notation; this seemed least confusing to me and is the same as the guide uses)

My question: How is this proved? I think that the idea here is that we're adding each node's least cost in and out edges (we need to both get to and leave each city). If those happen to be a neighbor's in or out edge, we divide by two to avoid double counting.

This intuition (why we divide by two) makes sense if the problem has three vertexes (since there are only three possible edges), but I'm not convinced this is a valid bound for larger graphs. Can someone please provide some intuition or a sketch of how this might be proved?

Best Answer

The proof/stems from the following $3$ observations about a tour $T$

  1. $T$ for each $v$, $T$ contains exactly two edges adjacent to $v$, and
  2. The sum of the weights of those two edges is at least the sum of the two lowest weights of edges adjacent to $v$.
  3. If $e_1(v)$ and $e_2(v)$ denote the edges adjacent to $v$ of smallest and second smallest weights (resp.) then either $e_1(v)$ and $e_2(v)$ are in $T$ or the sum of the weights of the two edges in $T$ adjacent to $v$ exceeds the sum of the weights $w_1(v)$ and $w_2(v)$ of $e_1(v)$ and $e_2(v)$.

Keeping (1) - (3) in mind, what is the total weight $W$ of $T$? If we denote by $w(e)$ the weight of an edge $e$ we might consider $$ \sum_{v \text{ in } T}[w(t_1(v)) + w(t_2(v))], $$ where $t_1(v)$ and $t_2(v)$ are the two distinct edges in $T$ adjacent to $v$. But since every edge in $T$ is adjacent to two vertices $v$, this sum contains the wait of each edge $e$ in $T$ twice, and hence equals $2W$. Since (3) is summarized by the statement $w(t_1(v)) + w(t_2(v)) \geq w_1(v) + w_2(v)$, we conclude

$$ W = \frac{1}{2}\sum_{v \text{ in } T}[w(t_1(v)) + w(t_2(v))] \geq \frac{1}{2}\sum_{v \text{ in } T}[w_1(v) + w_2(v)], $$ which is the desired lower bound.

Related Question