...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Traveling salesman games with the Monge property
【24h】

Traveling salesman games with the Monge property

机译：拥有Monge财产的旅行推销员游戏

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Several works have indicated the relationships between polynomially solvable combinatorial optimization problems and the core non-emptiness of cooperative games associated with them, and between intractable combinatorial optimization problems and the hardness of the problem to decide the core non-emptiness of the associated games. In this paper, we study the core of a traveling salesman game, which is associated with the traveling salesman problem. First, we show that in general the problem to test the core non-emptiness of a given traveling salesman game is N p-hard. This corresponds to the N p-hardness of the traveling salesman problem. Second, we show that the core of a traveling salesman game is non-empty if the distance matrix is a symmetric Monge matrix, and also that a traveling salesman game is submodular (or concave) if the distance matrix is a Kalmanson matrix. These correspond to the fact that the Monge property and the Kalmanson property are polynomially solvable special cases of the traveling salesman problem.
机译：多项工作表明了多项式可解决的组合优化问题和与之相关的合作博弈的核心非虚度之间的关系，以及棘手的组合优化问题与决定相关博弈的核心非虚度的问题之间的关系。在本文中，我们研究了一个与旅行商问题相关的旅行商游戏的核心。首先，我们证明，通常来说，测试给定的旅行推销员游戏的核心非空性的问题是N p-hard。这对应于旅行推销员问题的N p硬度。其次，我们证明，如果距离矩阵是对称的Monge矩阵，则旅行商的博弈的核心是非空的;如果距离矩阵是卡尔曼森矩阵，则旅行商的博弈是次模的（或凹的）。这些符合以下事实：Monge属性和Kalmanson属性是旅行商问题的多项式可解特例。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号