• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency
【24h】

Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency

机译：最优的软电弧一致性最小化局部定义的子模函数

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

摘要

Submodular function minimization is a polynomially solvable combinatorial problem. Unfortunately the best known general-purpose algorithms have high-order polynomial time complexity. In many applications the objective function is locally defined in that it is the sum of cost functions (also known as soft or valued constraints) whose arities are bounded by a constant. We prove that every valued constraint satisfaction problem with submodular cost functions has an equivalent instance on the same constraint scopes in which the actual minimum value of the objective function is rendered explicit. Such an equivalent instance is the result of establishing optimal soft arc consistency and can hence be found by solving a linear program. From a practical point of view, this provides us with an alternative algorithm for minimizing locally denned submodular functions. From a theoretical point of view, this brings to light a previously unknown connection between submodularity and soft arc consistency.
机译：亚模函数最小化是一个多项式可解决的组合问题。不幸的是，最著名的通用算法具有高阶多项式时间复杂度。在许多应用中，目标函数是局部定义的，因为它是成本函数的总和（也称为软约束或有值约束），其成本受常数限制。我们证明，每个具有亚模成本函数的约束满足满意问题在相同约束范围内都有一个等效实例，在该约束范围内，目标函数的实际最小值被明确表示。这种等效情况是建立最佳软电弧一致性的结果，因此可以通过求解线性程序来找到。从实际的角度来看，这为我们提供了一种用于最小化局部限定的子模函数的替代算法。从理论上讲，这揭示了子模量和软电弧一致性之间以前未知的联系。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号