...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >On the p-median polytope of Y-free graphs
【24h】

On the p-median polytope of Y-free graphs

机译：关于无Y图的p中位多态性

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

摘要

In this paper we consider a well-known class of valid inequalities for the p-median and the uncapacitated facility location polytopes, the odd cycle inequalities. It is known that their separation problem is polynomially solvable. We give a new polynomial separation algorithm based on a reduction from the original graph. Then, we define a non-trivial class of graphs, where the odd cycle inequalities together with the linear relaxations of both the p-median and uncapacitated facility location problems, suffice to describe the associated polytope. To do this, we first give a complete description of the fractional extreme points of the linear relaxation for the p-median polytope in this class of graphs.
机译：在本文中，我们考虑p-中位数和无能力设施位置多态性的一类有效不等式，即奇数周期不等式。已知它们的分离问题可以通过多项式解决。我们基于原始图的归约给出了一种新的多项式分离算法。然后，我们定义了一个非平凡的图类，其中奇数周期不等式以及p中值和无能力设施位置问题的线性松弛都足以描述相关的多面体。为此，我们首先完整地描述此类图中p中位数多位形的线性弛豫的分数极值点。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号