发帖
雷达卡
摘要翻译：
我们研究了两个不同约束条件结合的传播算法。不同约束的解可以看作变量/值二分图上的完美匹配。因此，我们研究了寻找同时二部匹配的问题。我们给出了著名的Hall定理的一个推广，它刻画了当同时存在二部匹配时的特征。不幸的是，寻找这样的匹配通常是NP困难的。然而，我们证明了一个惊人的结果，即在凸二部图上寻找同时匹配只需要多项式时间。基于这一理论结果，我们给出了第一个多项式时间界一致性算法。我们确定了一个病理问题，在这个问题上，这个传播子比现有的传播子快了几何级数。我们的实验表明，这种新的传播器可以提供显着的好处比现有的方法。
---
英文标题：
《Propagating Conjunctions of AllDifferent Constraints》
---
作者：
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 propagation algorithms for the conjunction of two AllDifferent constraints. Solutions of an AllDifferent constraint can be seen as perfect matchings on the variable/value bipartite graph. Therefore, we investigate the problem of finding simultaneous bipartite matchings. We present an extension of the famous Hall theorem which characterizes when simultaneous bipartite matchings exists. Unfortunately, finding such matchings is NP-hard in general. However, we prove a surprising result that finding a simultaneous matching on a convex bipartite graph takes just polynomial time. Based on this theoretical result, we provide the first polynomial time bound consistency algorithm for the conjunction of two AllDifferent constraints. We identify a pathological problem on which this propagator is exponentially faster compared to existing propagators. Our experiments show that this new propagator can offer significant benefits over existing methods.
---
PDF链接：
https://arxiv.org/pdf/1004.2626
京公网安备 11010802022788号
