发帖
雷达卡
摘要翻译：
我们研究了全局n值约束的分解。我们的主要贡献是理论上的：我们证明了像NVALUE这样的全局约束存在传播子，分解可以用同样的时间复杂度模拟，但空间复杂度要大得多。这表明全局传播者的好处往往不是节省时间，而是节省空间。我们的另一个理论贡献是首次证明了在最坏情况时间复杂度与界一致性相同的情况下，范围一致性可以在NVALUE上得到加强。最后，我们研究的分解很容易编码为线性不等式。因此，我们能够在整数线性规划中使用它们。
---
英文标题：
《Decomposition of the NVALUE constraint》
---
作者：
Christian Bessiere and George Katsirelos and Nina Narodytska and
Claude-Guy Quimper and Toby Walsh
---
最新提交年份：
2010
---
分类信息：
一级分类：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中的材料。
--
---
英文摘要：
We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate with the same time complexity but with a much greater space complexity. This suggests that the benefit of a global propagator may often not be in saving time but in saving space. Our other theoretical contribution is to show for the first time that range consistency can be enforced on NVALUE with the same worst-case time complexity as bound consistency. Finally, the decompositions we study are readily encoded as linear inequalities. We are therefore able to use them in integer linear programs.
---
PDF链接：
https://arxiv.org/pdf/1007.0603
京公网安备 11010802022788号
