I would like to understand why the Nearest Neighbour Algorithm has a logarithmic approximation ratio when given an instance of the metric travelling salesman problem. I have come across the paper of Rosenkrantz et al. : https://disco.ethz.ch/courses/fs16/podc/readingAssignment/1.pdf
What I have difficulty in is Lemma 1 in this paper in the part where the lower bound $\sum_{i \in H} \alpha_i l_i$ $\geq$ 2 $\sum_{i = k+1}^{min(2k, n)} \alpha_i l_i$ is given. Can anyone help in clarifying where this lower bound has come from? Why is it assumed in the paper that the first $k$, $l_i$'s have $\alpha_i$ = 0?
$k$ is at least half of the number of edges in $T$, otherwise $H$ would not be a complete subgraph on the node set. To obtain a lower bound now, we can just choose the $\alpha_i$ suitable.
$$\sum \alpha_i l_i = a_0 l_0 + \ldots + a_kl_k + \ldots + a_{\min(2k,n)} l_{\min(2k,n)} = 0 l_0 + \ldots + 0l_k + \ldots + 2 l_{k+1} + \ldots + 2 l_{\min(2k,n)}$$