A note on the Traveling Preacher Problem
Fekete, Sandor P. and Pulleyblank, William R.
(1998)
A note on the Traveling Preacher Problem.
Technical Report
, 5 p.
Abstract
In this paper, we consider a problem of cost allocations for shortest roundtrips. Given a weighted graph G=(V,E), we are to find a subset S of V with a maximum weight core element for the Traveling Preacher game, i.e., a subset S of V with a maximum cost allocation x(S) to the vertices, such that there is no nontrivial subset S' of S of vertices with a total cost allocation x(S') exceeding the cost of a Traveling Salesman tour visiting the vertices in the subset S. This game can be considered as a variant of the socalled Traveling Saleman game, with the difference that there is no specified central root node for the salesman. We show that this ''Traveling Preacher Problem'' can be solved in polynomial time, showing that the difficulty of finding a core allocation for a combinatorial optimization problem may be caused by the existence of a special depot node, rather than being a consequence of the hardness of the optimization problem itself.
Download: 
Postscript
Download (126kB)  Preview 

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

Citations:  5 (Google Scholar)  
Uncontrolled Keywords:  combinatorial optimization computational complexity cooperative games core allocation polynomial algorithms traveling salesman problem 
Subjects: 

Divisions:  UNSPECIFIED 
Related URLs: 
ZAIK Number:  zpr98331 

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