# Question

The Euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. Figure 15.9(a) shows the solution to a 7- point problem. The general problem is NP-complete, and its solution is therefore believed to require more than polynomial time (see Chapter 34).

Figure 15.9: Seven points in the plane, shown on a unit grid. (a) The shortest closed tour, with length approximately 24.89. This tour is not bitonic. (b) The shortest bitonic tour for the same set of points. Its length is approximately 25.58. J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. Figure 15.9(b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm is possible.

Describe an O (n2)-time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate.

Figure 15.9: Seven points in the plane, shown on a unit grid. (a) The shortest closed tour, with length approximately 24.89. This tour is not bitonic. (b) The shortest bitonic tour for the same set of points. Its length is approximately 25.58. J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. Figure 15.9(b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm is possible.

Describe an O (n2)-time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate.

## Answer to relevant Questions

Although merge sort runs in Θ (n lg n) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort ...In the depth-determination problem, we maintain a forest F = (Ti) of rooted trees under three operations:• MAKE-TREE (v) creates a tree whose only node is v.• FIND-DEPTH (v) returns the depth of node v within its ...Given an m × n matrix T over some field (such as the reals), show that (S,ℓ) is a matroid, where S is the set of columns of T and A ¬ℓ if and only if the columns in A are linearly independent.Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it 0). Show how to implement a counter as an array of bits so that any sequence of n INCREMENT and RESET operations takes ...Suppose we change line 4 of Dijkstra' s algorithm to the following. 4 while |Q| > 1. This change causes the while loop to execute |V | - 1 times instead of |V | times. Is this proposed algorithm correct?Post your question

0