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.


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 so-called 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: [img] Postscript
Download (126kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-331
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/331