...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains
【24h】

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains

机译：无限域上的子模函数和值约束满足问题

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

摘要

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. It is desirable to classify the computational complexity of VCSPs depending on a fixed set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified in this sense. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear homogeneous cost functions. We remark that in this paper the infinite domain will always be the set of rational numbers. We show that such VCSPs can be solved in polynomial time when the cost functions are additionally submodular, and that this is indeed a maximally tractable class: adding any cost function that is not submodular leads to an NP-hard VCSP.
机译：有价值的约束满足问题（VCSP）是一大类组合优化问题。希望根据输入中固定的一组允许的成本函数对VCSP的计算复杂度进行分类。最近，在这种意义上，已经对有限域上的有限成本函数集的所有VCSP的计算复杂度进行了分类。但是，许多自然优化问题无法在有限域上表述为VCSP。我们通过研究分段线性齐次成本函数的VCSP的复杂性，开始对无限域VCSP的系统研究。我们注意到，在本文中，无限域将始终是有理数的集合。我们表明，当成本函数额外为亚模时，此类VCSP可以在多项式时间内求解，而这确实是最大易处理的类：添加任何非亚模的成本函数会导致NP-hard VCSP。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号