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 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: |
Download (126kB) | Preview |
---|---|
Editorial actions: | ![]() |
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: | 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 |