• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Integer Programming and Combinatorial Optimization >Computational Aspects of Relaxation Complexity
【24h】

Computational Aspects of Relaxation Complexity

机译：放松复杂性的计算方面

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

摘要

The relaxation complexity rc(Ⅹ) of the set of integer points Ⅹ contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with Ⅹ. It is an important tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rc_Q(Ⅹ), a variant of rc(Ⅹ) in which the polyhedra P are required to be rational, and we show that rc(Ⅹ) can be computed in polynomial time if Ⅹ is 2-dimensional. We also present an explicit formula for rc(Ⅹ) of a specific class of sets Ⅹ and present numerical experiments on the distribution of rc(Ⅹ) in dimension 2.
机译：多面体中包含的整数点集合的弛豫复杂度RC（ⅹ）是任何多面体P的最小刻面，使得P中的整数点与ⅹ一致。 研究X的紧凑线性描述的存在是一个重要的工具。在本文中，我们在RC_Q（ⅹ）上导出紧密和可计算的上限，RC（ⅹ）的变体，其中Polyhedra P需要理性 ，并且我们表明如果ⅹ是二维，则可以在多项式时间中计算RC（ⅹ）。 我们还为特定类别的SETα的RC（ⅹ）的明确公式提供了关于尺寸2中RC（Ⅵ）的分布的数值实验。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号