[theory students] a question for the data scientists

[Eric Bach <bach@xxxxxxxxxxx>]

This semester my honors edition of 577 is using the traveling
salesman problem as a vehicle to teach algorithms.  Consideration
of TSP in R^1, for example, leads naturally to sorting.  The
following question came up.

   If X1,...,Xn are distinct real numbers, then the optimum tour
   through them has cost 2(max(Xi) - min(Xi)).  Sometimes in 577
   I show that max and min can be computed using 3n/2 + O(1)
   comparisons, and that no better result is possible.  What about
   computing the range ( = max - min )?  Does the 3n/2 bound still
   apply?  (Note that we need a more sophisticated model, one
   that allows arithmetic and comparisons.)

Someone must have thought about this before.  Do you know of anyone
who did?

Eric