Technical Note-On Traveling Salesman Games with Asymmetric Costs

• 成果类型: Article
• 署名作者: Toriello, Alejandro; Uhan, Nelson A.
• 署名单位: University System of Georgia; Georgia Institute of Technology; United States Department of Defense; United States Navy; United States Naval Academy
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2013.1225
• 发表日期: 2013
• 页码: 1429-1434
• 关键词: allocation; algorithms; tsp

摘要

We consider cooperative traveling salesman games with nonnegative 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.