发帖
雷达卡
摘要翻译：
我们指出无线网络中几个重要的资源分配问题都符合约束满足问题的一般框架。在这些应用程序中，变量位于不同的网络设备上，这些设备可能无法通信，但可能会干扰，受这些应用程序的要求启发，我们定义了CSP求解器为了实用而必须具备的自然准则。我们称这些算法为分散CSP求解器。最著名的CSP求解器是为集中式问题设计的，不符合这些标准。本文引入了一个随机分散CSP求解器，证明了它在有限时间内几乎可以找到一个解，并且证明了它具有许多实际需要的性质。我们在一个已被广泛研究的CSP类随机k-SAT上对该算法的性能进行了比较，说明了该算法在一千个变量的问题上寻找满意分配所花费的时间与随机集中求解器相比是竞争的，尽管它的性质是分散的。我们证明了求解器的实际效用，通过使用它为一个由曼哈顿市中心的数据组成的网络找到一个无干扰的信道分配。
---
英文标题：
《Decentralized Constraint Satisfaction》
---
作者：
K. R. Duffy and C. Bordenave and D. J. Leith
---
最新提交年份：
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中的材料。
--
---
英文摘要：
We show that several important resource allocation problems in wireless networks fit within the common framework of Constraint Satisfaction Problems (CSPs). Inspired by the requirements of these applications, where variables are located at distinct network devices that may not be able to communicate but may interfere, we define natural criteria that a CSP solver must possess in order to be practical. We term these algorithms decentralized CSP solvers. The best known CSP solvers were designed for centralized problems and do not meet these criteria. We introduce a stochastic decentralized CSP solver and prove that it will find a solution in almost surely finite time, should one exist, also showing it has many practically desirable properties. We benchmark the algorithm's performance on a well-studied class of CSPs, random k-SAT, illustrating that the time the algorithm takes to find a satisfying assignment is competitive with stochastic centralized solvers on problems with order a thousand variables despite its decentralized nature. We demonstrate the solver's practical utility for the problems that motivated its introduction by using it to find a non-interfering channel allocation for a network formed from data from downtown Manhattan.
---
PDF链接：
https://arxiv.org/pdf/1103.3240
京公网安备 11010802022788号
