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 S_n be a random variable denoting the length of this tour. Clearly, E[S_n] E[TST].

a.	Let d(Pj, Pj+1) be the distance between two consecutively visited points, Pj = (xj, yj) and Pj+1 = (xj+1, yj+1) in Sn. It is obvious that
b.	Now choose the most advantageous value of m and find an approximate upper bound for E[TST] for large n. (Assume that n >> 3.)
c.	Suppose now that instead of a unit square, the foregoing procedure were applied to a rectangular area of dimensions Xo by Yo. Show from (a) and (b) that if m is chosen correctly (what is the proper value of m?) the upper bound on E[TST] (i.e. E[Sn]) must be less than or equal to a quantity proportional to approximately 1.15 , where A = X0 Y0, for large n (n >> 3).