Optimization Online


On Traveling Salesman Games with Asymmetric Costs

Alejandro Toriello (alejandro.toriello***at***isye.gatech.edu)
Nelson A. Uhan (uhan***at***usna.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.

Download: [PDF]

Entry Submitted: 05/01/2012
Entry Accepted: 06/01/2012
Entry Last Modified: 07/24/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society