BUILDING BRIDGES BETWEEN CONVEX REGIONS

Abstract

In the Euclidean traveling salesman and buyers problem (TSBP), we are given a set of convex regions in d-dimensional space, and we wish to find a minimum-cost tour that visits all the regions. The cost of a tour depends on the length of the tour itself and on the distance that buyers within each region need to travel to meet the salesman. We show that constant-factor approximations to the TSBP and several similar problems can be obtained by visiting the centers of the smallest enclosing spheres of the regions.