Apply to Figure 8.38a the following approximation algorithms (Johnson and Papadimitriou, 1985; Rosenkrantz et al., 1977) to solve the traveling salesman problem. a. The nearest neighbor algorithm...

Apply to Figure 8.38a the following approximation algorithms (Johnson and Papadimitriou, 1985; Rosenkrantz et al., 1977) to solve the traveling salesman problem.

a. The nearest neighbor algorithm (next best method) begins with an arbitrary vertex v and then finds a vertex w not on the tour that is closest to the vertex u last added and includes in the tour edge(uw) and edge(wv) after deleting edge(vw).

b. The nearest insertion algorithm is obtained from nearestAdditionAlgorithm()

by minimizing

                            edge() + edge() – edge()

b. In this way, a new vertex
 is inserted in the best place in the existing tour, which may not be next to
.

c. The cheapest insertion algorithm is obtained from nearestAdditionAlgorithm() by including in tour a new vertex
 that minimizes the length of the new tour.

d. The farthest insertion algorithm is just like the nearest insertion algorithms except that it requires that
 is farthest from tour, not closest.

 e. The nearest merger algorithm, which corresponds to the Bor˚uvka algorithm: