发帖
雷达卡
摘要翻译：
在文献中已经提出并研究了约束满足问题的几种变体，用于建模那些解与某些给定成本相关的场景。在这些框架下，计算最优解通常是一个NP难问题；然而，当限制在约束相互作用可以通过（近）无环图建模的实例类上时，这个问题是可以在多项式时间内解决的。本文通过讨论基于超图无循环性的求解方法，以及更广泛的结构分解方法，如（超）树分解，挑出了更大类的易处理实例。
---
英文标题：
《Tractable Optimization Problems through Hypergraph-Based Structural
Restrictions》
---
作者：
Georg Gottlob and Gianluigi Greco and Francesco Scarcello
---
最新提交年份：
2012
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
Several variants of the Constraint Satisfaction Problem have been proposed and investigated in the literature for modelling those scenarios where solutions are associated with some given costs. Within these frameworks computing an optimal solution is an NP-hard problem in general; yet, when restricted over classes of instances whose constraint interactions can be modelled via (nearly-)acyclic graphs, this problem is known to be solvable in polynomial time. In this paper, larger classes of tractable instances are singled out, by discussing solution approaches based on exploiting hypergraph acyclicity and, more generally, structural decomposition methods, such as (hyper)tree decompositions.
---
PDF链接：
https://arxiv.org/pdf/1209.3419
京公网安备 11010802022788号
