5
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – cats Jan 3 '17 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.