The Guarantee and Its Scope
The nearest-neighbor rule is simple: from the current vertex, move to a closest vertex that has not yet been visited. Its simplicity does not make its performance independent of the instance size. For metric TSP, the worst-case approximation guarantee grows logarithmically with the number of vertices. Thus the bound is useful as a general guarantee, but it is not a constant-factor guarantee as the number of vertices grows.
Throughout, a metric TSP instance has a finite vertex set \(V\) with \(n=|V|\ge 2\), and a complete undirected graph whose edge lengths \(c(u,v)\) form a metric. In particular, \(c(u,v)=c(v,u)>0\) for distinct vertices, and the triangle inequality \(c(u,w)\le c(u,v)+c(v,w)\) holds for all vertices. A tour visits every vertex exactly once and returns to its starting vertex. Its cost is the sum of its edge lengths. Let \(\operatorname{OPT}\) denote the minimum cost of a tour.
The guarantee concerns the cost of the completed tour, including that final return edge. It holds for every starting vertex and every tie-breaking choice. It is an upper bound on the ratio to the optimal tour, not a claim that every nearest-neighbor tour has that ratio.
Here \(\lceil x\rceil\) is the least integer greater than or equal to \(x\). Since the edge lengths between distinct vertices are positive and there are at least two vertices, \(\operatorname{OPT}>0\), so the ratio is defined. When \(n=1\), the unique tour has cost \(0\); a ratio to \(\operatorname{OPT}=0\) is not defined, so the theorem is stated for \(n\ge2\).
Why a Logarithm Appears
The proof rests on one property of the nearest-neighbor rule: when a long edge is chosen from a vertex, every vertex still to be visited is at least that far away. Vertices whose nearest-neighbor edges are all long are therefore far apart from one another, and a short tour cannot pass through many vertices that are all far apart. Sorting the nearest-neighbor edge lengths and cutting the list into blocks of sizes \(1,1,2,4,8,\ldots\) shows that each block costs at most half of \(\operatorname{OPT}\). There are about \(\log_2 n\) blocks.
Write the nearest-neighbor tour as \(v_1,v_2,\ldots,v_n\) and return to \(v_1\). For each vertex \(v_i\) let \(a_i\) be the length of the edge leaving it: \(a_i=c(v_i,v_{i+1})\) for \(i<n\), and \(a_n=c(v_n,v_1)\) is the return edge. Then \(c(T_{\mathrm{NN}})=a_1+\cdots+a_n\).
Proof. Since \(i<j\le n\), we have \(i\le n-1\), so \(a_i=c(v_i,v_{i+1})\) is the length of a nearest-neighbor choice. When the run is at \(v_i\), the vertex \(v_{i+1}\) is a nearest unvisited vertex, and \(v_j\) is unvisited because \(j>i\). Hence \(a_i\le c(v_i,v_j)\). The second inequality is immediate. \(\square\)
Proof. An optimal tour consists of two paths between \(u\) and \(w\). By the triangle inequality each has length at least \(c(u,w)\), so \(\operatorname{OPT}\ge2c(u,w)\). \(\square\)
Proof. List the vertices of \(Q\) in the order in which an optimal tour visits them, \(u_1,\ldots,u_q\), and set \(u_{q+1}=u_1\). By the triangle inequality, the tour has length at least \(\sum_{r=1}^{q}c(u_r,u_{r+1})\). By Lemma 1, any two distinct vertices \(u,w\) satisfy \(c(u,w)\ge\min(a_u,a_w)\). Hence the tour has length at least \(\sum_{r=1}^{q}m_r\), where \(m_r=\min(a_{u_r},a_{u_{r+1}})\).
Sort the \(q\) numbers \(m_r\) increasingly as \(m_{(1)}\le\cdots\le m_{(q)}\). We claim \(m_{(r)}\ge x_{\lceil r/2\rceil}\) for each \(r\). Suppose instead that \(m_{(r)}<x_s\) with \(s=\lceil r/2\rceil\). Then at least \(r\) of the pairs \((u_k,u_{k+1})\) have \(m_k<x_s\), and each of those pairs contains a vertex \(u\) with \(a_u<x_s\). At most \(s-1\) vertices of \(Q\) have \(a_u<x_s\), and each vertex lies in exactly two of the pairs. So at most \(2(s-1)\) pairs can contain such a vertex. But \(r\ge2s-1>2(s-1)\), a contradiction.
Therefore \(\sum_{r=1}^q m_{(r)}\ge\sum_{r=1}^{2t}x_{\lceil r/2\rceil}=2(x_1+\cdots+x_t)\), using \(2t\le q\) and \(m_{(r)}\ge0\). \(\square\)
Proof of the theorem. Sort all \(n\) numbers \(a_1,\ldots,a_n\) decreasingly as \(b_1\ge b_2\ge\cdots\ge b_n\), so that \(c(T_{\mathrm{NN}})=b_1+\cdots+b_n\). By Lemma 2, \(b_1\le\tfrac12\operatorname{OPT}\).
For each \(i\ge0\) with \(2^i<n\), let \(q_i=\min(2^{i+1},n)\) and \(t_i=q_i-2^i\), and consider the block \(b_{2^i+1},\ldots,b_{q_i}\). Let \(Q\) be a set of \(q_i\) vertices whose values are \(b_1,\ldots,b_{q_i}\). Then \(q_i\ge2\), and the \(t_i\) smallest values in \(Q\) are exactly the block. Also \(t_i\le\lfloor q_i/2\rfloor\): if \(q_i=2^{i+1}\), then \(t_i=q_i/2\); if \(q_i=n<2^{i+1}\), then \(t_i=n-2^i\le n/2\), and \(t_i\) is an integer. Lemma 3 gives $$ b_{2^i+1}+\cdots+b_{q_i}\le\tfrac12\operatorname{OPT}. $$ The values of \(i\) with \(2^i<n\) are \(i=0,1,\ldots,\lceil\log_2 n\rceil-1\), so there are \(\lceil\log_2 n\rceil\) blocks, and together with \(b_1\) they cover \(b_1,\ldots,b_n\). Adding, $$ c(T_{\mathrm{NN}})\le\tfrac12\operatorname{OPT}+\lceil\log_2 n\rceil\cdot\tfrac12\operatorname{OPT}=\frac{1+\lceil\log_2 n\rceil}{2}\operatorname{OPT}. $$ This holds for every start and every tie-breaking choice, since the lemmas used only the order in which the run visited the vertices. \(\square\)
The sum includes the return edge \(a_n\), which is essential: the bound is for the completed tour. The ceiling makes the bound a step function of \(n\): it changes when \(n\) passes a power of two, rather than increasing at every new vertex.
Worked Applications
Worked Example: Computing the Bound for Four Vertices
For \(n=4\), \(\log_2 4=2\), so \(\lceil\log_2 4\rceil=2\). The guaranteed ratio is therefore at most $$ \frac{1}{2}(1+2)=\frac{3}{2}. $$ A nearest-neighbor tour on any four-vertex metric instance has cost at most \(1.5\operatorname{OPT}\). This is a guarantee, not a prediction that the algorithm will cost \(1.5\operatorname{OPT}\).
For a direct check on an instance, take \(V=\{0,1,2,3\}\) with the complete-graph lengths \(c(i,j)=|i-j|\). Starting at \(0\), the choices are \(0\to1\), \(1\to2\), and \(2\to3\), of lengths \(1,1,1\). The return edge \(3\to0\) has length \(3\), so the tour costs \(1+1+1+3=6\).
The tour \(0\to1\to2\to3\to0\) is optimal. In any tour, the two paths between \(0\) and \(3\) each have length at least \(c(0,3)=3\), by the triangle inequality, so every tour costs at least \(6\). The displayed tour attains this, so \(\operatorname{OPT}=6\). The ratio is \(6/6=1\), which is below the bound \(3/2\). The calculation also verifies that the return edge cannot be omitted.
Worked Example: The Ceiling at Nine Vertices
For \(n=9\), \(2^3=8<9\le16=2^4\). Hence \(\lceil\log_2 9\rceil=4\), and the guarantee is $$ \frac{1}{2}(1+4)=\frac{5}{2}. $$ It is not correct to use \(3\) in place of the ceiling: \(\log_2 9\) is greater than \(3\), so its ceiling is \(4\).
For comparison, at \(n=8\), \(\lceil\log_2 8\rceil=3\), giving the bound \(\frac12(1+3)=2\). Thus increasing the vertex count from \(8\) to \(9\) increases this worst-case guarantee from \(2\) to \(2.5\). It does not imply that a particular nine-vertex instance has a worse nearest-neighbor tour than every eight-vertex instance.
Check: \(2^3=8\) and \(2^4=16\), so \(8<9\le16\), confirming that \(4\) is the least integer \(k\) with \(9\le2^k\). For \(n=8\), \(8\le2^3\), and \(3\) is the least such integer.
Worked Example: A Six-Vertex Metric with a Tie
Let \(V=\{o,a,b,c,d,e\}\), and define the complete-graph lengths by \(c(o,x)=1\) for each leaf \(x\in\{a,b,c,d,e\}\), and \(c(x,y)=2\) for distinct leaves \(x,y\). These lengths form a metric: a leaf-to-leaf distance is \(2=1+1\), and the triangle inequality involving a center-to-leaf edge follows because \(1\le1+2\). Start at \(o\), and break ties by choosing \(a,b,c,d,e\) in that order.
The first choice \(o\to a\) has length \(1\). From \(a\), each unvisited leaf is at distance \(2\), so choose \(b\); the next choices are \(b\to c\), \(c\to d\), and \(d\to e\), each of length \(2\). The return \(e\to o\) has length \(1\). The tour cost is \(1+2+2+2+2+1=10\).
This tour is optimal. Every tour has two edges incident with \(o\), each of length \(1\), and its other four edges join leaves, each of length \(2\). Thus every tour costs \(2\cdot1+4\cdot2=10\), matching the nearest-neighbor tour. For \(n=6\), \(2^2=4<6\le8=2^3\), so the bound is \(\frac12(1+3)=2\). The actual ratio \(10/10=1\) is within that bound.
Interpreting the Dependence on \(n\)
The bound grows like one half of the base-two logarithm of \(n\), up to the ceiling and the additive one. Doubling \(n\) can increase the ceiling by one, and therefore increase the stated factor by \(1/2\). In particular, the theorem guarantees a finite ratio for every finite instance, but its right-hand side is not bounded by one fixed constant as \(n\) ranges over all positive integers.
This is a worst-case statement. It does not say that the nearest-neighbor heuristic becomes steadily worse on ordinary instances, nor that the bound is attained for every \(n\). The examples above include instances where the algorithm is optimal even though the general guarantee is larger than \(1\). Starting-vertex choice and tie-breaking can change the output, but the theorem holds uniformly over those choices.
Common Pitfalls
Leaving out the return edge. The sequence of nearest-neighbor choices creates a path, not yet a tour. In the four-point line example, the path costs \(3\), but the return edge costs \(3\), making the tour cost \(6\). A bound on the path alone is not a bound on the completed tour unless the return is included in the analysis.
Using the floor instead of the ceiling. At \(n=9\), \(\log_2 9>3\), so the relevant integer is \(4\), not \(3\). A reliable check is to find the smallest integer \(k\) for which \(n\le2^k\).
Assuming the metric condition is optional. The triangle inequality is part of the hypotheses used in the proof, in Lemmas 2 and 3. Without it, replacing a route by a direct edge can increase its length, and this metric guarantee does not apply.
Shortcutting an open walk. Shortcutting repeated vertices in a closed walk that visits every vertex can produce a tour of no greater length: the triangle inequality bounds each shortcut by the portion of the walk it replaces, including the final return to the starting vertex. The same assertion is false for an open walk. For instance, with two vertices at distance \(1\), the open walk between them costs \(1\), while a tour must return and costs \(2\). The closed-walk hypothesis cannot be dropped.
Check Your Understanding
Use the theorem and the definitions in this tutorial to answer the following questions.
- Compute the stated nearest-neighbor bound for \(n=16\) and \(n=17\). Identify the ceiling in each case.
- Why must the cost used in the approximation ratio include the edge from the last visited vertex back to the start?
- For the six-vertex metric above, what is the nearest-neighbor tour cost if the start is a leaf and the algorithm next chooses \(o\)?
- Does the theorem say that every nearest-neighbor tour has cost exactly \(\frac12(1+\lceil\log_2 n\rceil)\operatorname{OPT}\)? Explain.
- Which lemmas in the proof use the triangle inequality, and where does the nearest-neighbor rule itself enter?