%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 }