2013 | OriginalPaper | Chapter
Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
Authors : Pegah Kamousi, Subhash Suri
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the problem of planning a shortest tour through a collection of neighborhoods in the plane, where each neighborhood is a disk whose radius is an
i
.
i
.
d
. random variable drawn from a known probability distribution. This is a
stochastic
version of the classic traveling salesman problem with neighborhoods (TSPN). Planning such tours under uncertainty, a fundamental problem in its own right, is motivated by a number of applications including the following data gathering problem in sensor networks: a robotic
data mule
needs to collect data from
n
geographically distributed wireless sensor nodes whose communication range
r
is a random variable influenced by environmental factors.
We propose a polynomial-time algorithm that achieves a factor
O
(loglog
n
) approximation of the
expected length of an optimal tour
. In data mule applications, the problem has an additional complexity: the radii of the disks are only
revealed
when the robot reaches the disk boundary (transmission success). For this
online
version of the stochastic TSPN, we achieve an approximation ratio of
O
(log
n
). In the special case, where the disks with their
mean radii
are disjoint, we achieve an
O
(1) approximation even for the online case.