Title: TSP With Locational Uncertainty: The Adversarial Model,
Abstract: In this paper we study a natural special case of the Traveling Salesman
Problem (TSP) with point-locational-uncertainty which we will call the {\em
adversarial TSP} problem (ATSP). Given a metric space $(X, d)$ and a set of
subsets $R = \{R_1, R_2, ... , R_n\} : R_i \subseteq X$, the goal is to devise
an ordering of the regions, $\sigma_R$, that the tour will visit such that when
a single point is chosen from each region, the induced tour over those points
in the ordering prescribed by $\sigma_R$ is as short as possible. Unlike the
classical locational-uncertainty-TSP problem, which focuses on minimizing the
expected length of such a tour when the point within each region is chosen
according to some probability distribution, here, we focus on the {\em
adversarial model} in which once the choice of $\sigma_R$ is announced, an
adversary selects a point from each region in order to make the resulting tour
as long as possible. In other words, we consider an offline problem in which
the goal is to determine an ordering of the regions $R$ that is optimal with
respect to the "worst" point possible within each region being chosen by an
adversary, who knows the chosen ordering. We give a $3$-approximation when $R$
is a set of arbitrary regions/sets of points in a metric space. We show how
geometry leads to improved constant factor approximations when regions are
parallel line segments of the same lengths, and a polynomial-time approximation
scheme (PTAS) for the important special case in which $R$ is a set of disjoint
unit disks in the plane.