...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical Programming >Small Chvátal Rank
【24h】

Small Chvátal Rank

机译：小勇士等级

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We propose a variant of the Chvátal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {x: A x ≤ b} as b varies. The number of steps needed is called the small Chvátal rank (SCR) of A. We characterize matrices for which SCR is zero via the notion of supernormality which generalizes unimodularity. SCR is studied in the context of the stable set problem in a graph, and we show that many of the well-known facet normals of the stable set polytope appear in at most two rounds of our procedure. Our results reveal a uniform hypercyclic structure behind the normals of many complicated facet inequalities in the literature for the stable set polytope. Lower bounds for SCR are derived both in general and for polytopes in the unit cube.
机译：我们提出了一种Chvátal-Gomory程序的变体，当b变化时，它将为所有多面体{x：A x≤b}的整数壳生成足够的面法线集。所需的步数称为A的小Chvátal等级（SCR）。我们通过超常态性的概念来概括SCR为零的矩阵，该概念推广了单模量。在图中以稳定集问题为背景对SCR进行了研究，结果表明，稳定集多面体的许多众所周知的面法线最多出现在我们的过程的两轮中。我们的结果揭示了稳定的多态性在文献中许多复杂的面不等式的法线之后的统一超环结构。 SCR的下限通常可以推导，也可以推导单位立方体中的多面体的下限。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号