4
$\begingroup$

I encountered a problem, where I am given a (fully-connected) graph within a metric space, where each edge weight is either 1 or 2.

My task is to prove that the following greedy algorithm gives a $\frac{3}{2}$-approximation for finding a TSP path: Start from an arbitrary node, pick the nearest neighbour node, go to this node and pick its nearest neighbour. Procedure is repeated until all nodes are picked, so that a valid cycle is produced.

I have seen more advanced techniques to solve the problem more efficiently here, which, however, did not help me.

My attempt was: Take any 3 nodes. Since we have a fully connected graph, the edges between the 3 nodes must form a triangle, and since we have a metric space, possible triangle sides are: $\{ (1,1,1), (2,2,2), (2,2,1) \}$. Since we are looking for path, we will never take all sides of this triangle, but at most 2. Since we always make our choice greedily, if the triangle is with sides $(2,2,1)$, we will never pick the 2 sides of length 2 together, but we will pick a side of length 1, and a side of length 2, hence resulting of weight from this triangle is 3.

I am stopping here, as I am not confident already.

$\endgroup$
1
  • $\begingroup$ $(1,1,2)$ is also possible in a metric space. $\endgroup$
    – John L.
    Commented Mar 11, 2022 at 7:11

1 Answer 1

3
$\begingroup$

Call an edge of weight $1$ a light edge.
Call a node incident to a light edge a light node.
Suppose the optimal travelling cycle contains $k$ light edges.

Consider those $k$ edges. Since these edges are part of a cycle, a node is incident to at most two of them. Since every edge is incident to two nodes, there are at least $k$ nodes that are incident to them. That is, there are at last $k$ light nodes.

For each light node, the greedy algorithm will choose at least one light edge incident to it unless it is the last node chosen by the greedy algorithm. So at least $(k-1)/2$ light edges will be selected by the greedy algorithm.

Let $n$ be the number of nodes in the graph. Since the number of edges in the travelling cycle is $n$, $k\le n$.
The weight of the optimal travelling cycle is $2n - k$.
The weight of the cycle selected by the greedy algorithm is at most $2n - (k-1)/2$.

$$(2n-(k-1)/2)- \frac32(2n-k)=\frac{k+1}2-n\le \frac{n+n}2-n=0. \quad\checkmark$$.

$\endgroup$
2
  • $\begingroup$ The principle is super clear. Thanks @John However, the formula is not precise enough. $k \leq n + n -2 \Rightarrow k + 2n + \frac{3}{2}k - \frac{1}{2} \leq n + n - 2 + 2n - \frac{3}{2}k - \frac{1}{2} \Rightarrow 2n - \frac{k-1}{2} \leq n + \frac{3}{2}(2n - k)$. Which is not what we want to show. I believe that we should have started with $k \leq n$. $\endgroup$
    – NiRvanA
    Commented Mar 11, 2022 at 20:46
  • 1
    $\begingroup$ @IIK Thanks for the feedback. Is the last step clearer now? $\endgroup$
    – John L.
    Commented Mar 11, 2022 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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