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 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.

Actions:

Download:	Postscript Download (126kB) | Preview
Editorial actions:	View Item (Login required)