6.7 Upper bound on the expected length of the TST A total of n points are randomly and uniformly distributed within a unit square. We wish to obtain an upper bound on the expected length of the optimum traveling salesman tour, E[TST], through these n points.
Suppose that we divide the unit square into m equal-width columns, as shown on Figure P6.7, where m is to be determined later. We visit all n points through the following strategy. We start from the point in the leftmost column having the largest y coordinate. We then visit the point in the same column having the next lower y coordinate, and so on. When we reach the lowest point in the first column, we next visit the lowest point in the second column and we then traverse the points in that column upward. We continue this process by visiting all columns from left to right, changing the direction of traversal at each column. To complete the tour, we join the last point to the first point with a straight line.
Let Sn be a random variable denoting the length of this tour. Clearly, E[Sn] E[TST].