On Traveling Salesman Games with Asymmetric Costs
Alejandro Toriello (alejandro.torielloisye.gatech.edu)
Abstract: We consider cooperative traveling salesman games with non-negative asymmetric costs satisfying the triangle inequality. We construct a stable cost allocation with budget balance guarantee equal to the Held-Karp integrality gap for the asymmetric traveling salesman problem, using the parsimonious property and a previously unknown connection to linear production games. We also show that our techniques extend to larger classes of network design games. We then provide a simple example showing that our cost allocation does not necessarily achieve the best possible budget balance guarantee, even among cost allocations stable for the game defined by the Held-Karp relaxation, and discuss its implications on future work on traveling salesman games.
Keywords: cooperative games; traveling salesman problem; Held-Karp bound
Category 1: Other Topics (Game Theory )
Category 2: Integer Programming
Category 3: Combinatorial Optimization
Citation: Submitted April 2012. Revised March 2013. Revised July 2013.
Entry Submitted: 05/01/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|