...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Cardinality constrained minimum cut problems: complexity and algorithms
【24h】

Cardinality constrained minimum cut problems: complexity and algorithms

机译：基数约束最小割问题：复杂性和算法

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

摘要

In several applications the solutions of combinatorial optimization problems (COP) are required to satisfy an additional cardinality constraint, that is to contain a fixed number of elements. So far the family of (COP) with cardinality constraints has been little investigated. The present work tackles a new problem of this class: the k-cardinality minimum cut problem (k-card cut). For a number of variants of this problem we show complexity results in the most significant graph classes. Moreover, we develop several heuristic algorithms for the k-card cut problem for complete, complete bipartite, and general graphs. Lower bounds are obtained through an SDP formulation, and used to show the quality of the heuristics. Finally, we present a randomized SDP heuristic and numerical results.
机译：在一些应用中，需要组合优化问题（COP）的解决方案来满足附加的基数约束，即包含固定数量的元素。到目前为止，对具有基数约束的（COP）家族的研究很少。当前的工作解决了这一类的新问题：k基数最小割问题（k卡割）。对于此问题的许多变体，我们在最重要的图类中显示了复杂性结果。此外，我们针对完整，完整的二部图和一般图针对k卡切割问题开发了几种启发式算法。下限是通过SDP公式获得的，用于显示启发式方法的质量。最后，我们提出了随机的SDP启发式方法和数值结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号