# Traveling Salesman Variant - Greedy Algorithm based on Least Cost better than that based on Highest

This is a rather intuitive statement about the traveling salesman problem that is surprisingly tricky to prove. I haven't seen this anywhere else, so I thought I would share it. The source is an old Russian olympiad (1970s?).

There are two Russian moguls, wanting to conduct a tour of their home country's cities (without returning to their origin city, and without visiting a city a twice). Suppose every two cities are connected by a fixed flight cost (in either direction) . The first follows the greedy algorithm: always choose the cheapest flight available from your current city. The second does the opposite: always choose the most expensive available flight. Prove that the first spends no more than the second.

• There were no moguls in 70s Russia. Such language indicates 90s. – user58697 Dec 9 '16 at 20:51

Let $K_n$ be a complete, undirected weighted graph. Starting from a vertex $v$ construct a greedy Hamiltonian path $P$ by always selecting the cheapest edge leading to a yet uncovered vertex. Starting from a vertex $u$ (which may be equal to $v$ or not) construct an anti-greedy Hamiltonian path $Q$ by always selecting the most expensive edge leading to a yet uncovered vertex. We show that the total weight of $P$ is at most the total weight of $Q$.
Without loss of generality we may assume that all weights are positive reals. For a set of edges $F$ and a real $x$ let $f(x, F)$ denote the number of edges in $F$ whose weight is at least $x$. It is easy to see that the total weight of the edges in $F$ is exactly$$\int_0^\infty f(x, F)\,dx.$$Thus, in order to prove the desired result it suffices to show that for any fixed $x$,$$f(x, P) \le f(x, Q).$$We proceed with a proof of that. Let $P(x)$ denote the set of all edges of $P$ whose weight is at least $x$. Then $P(x)$ is a union of connected components, and each of them is a path. Let$$C = c_1c_2 \ldots c_k$$be such a path that forms a component with at least one edge, thus$$|C| = k \ge 2.$$Assume that $C$ was selected greedily in this order, from $c_1$ to $c_k$. Note that the weight of every edge $c_ic_j$ with $1 \le i < j \le k$ is at least $x$. Indeed, this weight is at least the weight of $c_ic_{i + 1}$, as $P$ was chosen greedily. Consider now the path $Q$ chosen anti-greedily. As $Q$ is a Hamiltonian path all the vertices of $C$ appear in $Q$ in some order. We claim that for every $i$, $1 \le i < k$, the edge of $Q$ emanating from the vertex of $C$ that appears in place number $i$ in this order is of weight at least $x$. Indeed, when we chose this edge anti-greedily, there was still at least one yet uncovered vertex of $C$ and by the argument above the weight of the edge leading to it is at least $x$. Thus the weight of the edge chosen was at least $x$. This means that among the edges emanating from vertices of $C$ at least $k - 1$ have weight at least $x$, and as $C$ has $k - 1$ edges, summing over all components implies that indeed$$f(x, Q) \ge f(x, P),$$completing the proof.
• This is basically the solution I know, but it might be easier to note that this is the same as showing that the $k$th cheapest flight taken by the cheaper one is cheaper than the $k$th cheapest of the other. You don't need the integral or to split into connected components then. – cats Jan 3 '17 at 22:36