APPROXIMATION ALGORITHMS FOR THE GEOMETRIC COVERING SALESMAN PROBLEM

We introduce a geometric version of the Covering Salesman Problem: Eac h of the n salesman's clients specifies a neighborhood in which they a re willing to meet the salesman. Identifying a tour of minimum length that visits all neighboirhoods is an NP-hard problem, since it is a ge neralization of the Traveling Salesman Problem. We present simple heur istic procedures for constructing tours, for a variety of neighborhood types, whose length is guaranteed to be within a constant factor of t he length of an optimal tour. The neighborhoods we consider include pa rallel unit segments, translates of a polygonal region, and circles.