The Traveling Salesman Problem under squared Euclidean distances

In case the cities correspond to points in the (Euclidean) plane and their distances correspond to "normal" (Euclidean) distances, a shortest round-trip can be approximated arbitrarily well thanks to the ground-breaking result of Sanjeev Arora.  The top half of the figure on the right shows a very simple point set and (in light blue) the resulting shortest round-trip with respect to Euclidean distances.

In the context of wireless ad-hoc networks, squared Euclidean distances have been investigated a lot because they better reflect the energy consumption in wireless communication.  With colleagues from the Netherlands, Alexander Wolff considered the famous traveling salesman problem with respect to these distances. In the bottom half of the figure on the right, a shortest round-trip with respect to squared Euclidean distances is indicated by the orange curve.

The main result of the conference contribution is an efficient algorithm that computes for any set of points in the plane a round-trip whose length (measured in the squared Euclidean sense) is at most 5 times as long as a shortest round-trip.  So far, the best algorithm guaranteed a bound of 6 times the length of a shortest round-trip.

More information can be found in the slides of his talk and in the conference article (joint work with Mark de Berg, Fred van Nijnatten, René Sitters, and Gerhard Woeginger).