期刊
OPERATIONS RESEARCH
卷 61, 期 6, 页码 1429-1434出版社
INFORMS
DOI: 10.1287/opre.2013.1225
关键词
-
资金
- National Science Foundation [CMMI-1265616]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1265616] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据