We introduce a geometric version of the Covering Salesman Problem: Each of the n salesman's clients specifies a neighborhood in which they are willing to meet the salesman. Identifying a tour of minimum length that visits all neighboirhoods is an NP-hard problem, since it is a generalization of the Traveling Salesman Problem. We present simple heuristic procedures for constructing tours, for a variety of neighborhood types, whose length is guaranteed to be within a constant factor of the length of an optimal tour. The neighborhoods we consider include parallel unit segments, translates of a polygonal region, and circles.
%0 Journal Article
%1 ARKIN1994197
%A Arkin, Esther M.
%A Hassin, Refael
%D 1994
%J Discrete Applied Mathematics
%K algorithms stackercrane tsp
%N 3
%P 197 - 218
%R http://dx.doi.org/10.1016/0166-218X(94)90008-6
%T Approximation algorithms for the geometric covering salesman problem
%U http://www.sciencedirect.com/science/article/pii/0166218X94900086
%V 55
%X We introduce a geometric version of the Covering Salesman Problem: Each of the n salesman's clients specifies a neighborhood in which they are willing to meet the salesman. Identifying a tour of minimum length that visits all neighboirhoods is an NP-hard problem, since it is a generalization of the Traveling Salesman Problem. We present simple heuristic procedures for constructing tours, for a variety of neighborhood types, whose length is guaranteed to be within a constant factor of the length of an optimal tour. The neighborhoods we consider include parallel unit segments, translates of a polygonal region, and circles.
@article{ARKIN1994197,
abstract = {We introduce a geometric version of the Covering Salesman Problem: Each of the n salesman's clients specifies a neighborhood in which they are willing to meet the salesman. Identifying a tour of minimum length that visits all neighboirhoods is an NP-hard problem, since it is a generalization of the Traveling Salesman Problem. We present simple heuristic procedures for constructing tours, for a variety of neighborhood types, whose length is guaranteed to be within a constant factor of the length of an optimal tour. The neighborhoods we consider include parallel unit segments, translates of a polygonal region, and circles.},
added-at = {2016-04-12T20:14:47.000+0200},
author = {Arkin, Esther M. and Hassin, Refael},
biburl = {https://www.bibsonomy.org/bibtex/25b28bf38e4c82ced3ad88e666576002f/prathyush},
doi = {http://dx.doi.org/10.1016/0166-218X(94)90008-6},
interhash = {91ee0849787f0b5949b230e1cdc1086c},
intrahash = {5b28bf38e4c82ced3ad88e666576002f},
issn = {0166-218X},
journal = {Discrete Applied Mathematics},
keywords = {algorithms stackercrane tsp},
number = 3,
pages = {197 - 218},
timestamp = {2016-04-12T20:14:47.000+0200},
title = {Approximation algorithms for the geometric covering salesman problem},
url = {http://www.sciencedirect.com/science/article/pii/0166218X94900086},
volume = 55,
year = 1994
}