Traveling Salesmen in the Age of Competition
Fekete, Sandor P. and Schmitt, Matthias
(1997)
Traveling Salesmen in the Age of Competition.
Technical Report
, 5 p.
Abstract
We propose the ''Competing Salesmen Problem'' (CSP), a 2player competitive version of the classical Travelling Salesman Problem. This problem arises when we are considering two competing salesmen instead of just one. The concern for a shortest tour is replaced by the necessity to reach any of the customers before the opponent does. In particular, we consider the situation where players are taking turns, moving one edge at a time within a graph G=(V,E). The set of customers is given by a subset VC of the vertices V. At any given time, both players know of their opponent's position. A player wins if he is able to reach more vertices of VC before the opponent does. We prove that certain decision problems of this type are NPcomplete; we conjecture that the general problem is PSPACEcomplete. Furthermore, we show that the starting player may lose the game, even if both players start from the same vertex. For special cases, we can give a number of positive results: If G is a tree T and both players start from the same vertex, we can show that the starting player can avoid a loss. On the other hand, we can show that the second player can avoid to lose by more than one customer, provided that VC consists of leaves of the tree T. It is unclear whether a polynomial strategy exists for any of the two players to force this outcome, and we point out some of the difficulties. For the case where T is a star (i.e. a tree with only one vertex of degree higher than 2) and VC consists of n leaves of T, we give a simple and fast O(n log n) strategy which is optimal for both players. We conclude by discussing geometric variants of the problem.
Download: 
Postscript
Download (124kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  3 (Google Scholar)  
Uncontrolled Keywords:  combinatorial games traveling salesman problem 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr97266 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:45 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/266 