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.


We propose the ''Competing Salesmen Problem'' (CSP), a 2-player 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 NP-complete; we conjecture that the general problem is PSPACE-complete. 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: [img] Postscript
Download (124kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-266
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45