# TSP With Point Locational Uncertainty: The Adversarial Model

## Tyler Mayer, Stony Brook University

## March 7, 2017

We study a natural special case of the Traveling Salesman Problem
(TSP) with point-locational-uncertainty which we will call the *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 known probability distribution, here, we
focus on the adversarial model where once $\sigma_R$ is prescribed,
an adversary selects a point from each region in order to make the
resulting tour as long as possible. In other words we assume the
worst point possible within each region, with respect to the ordering
of the regions prescribed, will be chosen by an adversary as part of
an offline problem. We give a $3 + \frac1n$-approximation when $R$ is a
set arbitrary regions/sets of points in a metric space. We show how
geometry leads to improved constant factor approximations when
regions are disjoint unit line segments of the same orientation, and
a polynomial time approximation scheme (PTAS) for the important
special case when $R$ is a set of disjoint unit disks in the plane.