摘要翻译:
我们考虑原型组合优化问题的一个变体,称为图着色。我们的优化目标是用固定数量的颜色给图的顶点着色,以使每个给定顶点的最近邻集中存在的不同颜色的数量最大化。这个问题,我们形象地称之为“调色板着色”,最近作为分布式数据存储上下文中出现的问题的一个基本例子得到了解决。尽管它尚未被证明是NP完全的,但随机搜索算法发现该问题很难解决。基于朴素信念传播算法的启发式算法在一定条件下运行良好。本文在上述结果的基础上,提出了正确的信念传播算法,该算法需要考虑问题中存在的约束的多体性质。该方法以增加计算量为代价,改进了朴素信念传播方法。我们还研究了在大尺寸(“热力学”)极限下,稀疏随机图的不同系综的可满足到不可满足的“相变”作为顶点平均度的函数的出现。
---
英文标题:
《Palette-colouring: a belief-propagation approach》
---
作者:
Alessandro Pelizzola, Marco Pretti, and Jort van Mourik
---
最新提交年份:
2011
---
分类信息:
一级分类:Physics 物理学
二级分类:Statistical Mechanics 统计力学
分类描述:Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变,热力学,场论,非平衡现象,重整化群和标度,可积模型,湍流
--
一级分类: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中的材料。
--
一级分类:Computer Science 计算机科学
二级分类:Data Structures and Algorithms 数据结构与算法
分类描述:Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类:Mathematics 数学
二级分类:Combinatorics 组合学
分类描述:Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
离散数学,图论,计数,组合优化,拉姆齐理论,组合对策论
--
---
英文摘要:
We consider a variation of the prototype combinatorial-optimisation problem known as graph-colouring. Our optimisation goal is to colour the vertices of a graph with a fixed number of colours, in a way to maximise the number of different colours present in the set of nearest neighbours of each given vertex. This problem, which we pictorially call "palette-colouring", has been recently addressed as a basic example of problem arising in the context of distributed data storage. Even though it has not been proved to be NP complete, random search algorithms find the problem hard to solve. Heuristics based on a naive belief propagation algorithm are observed to work quite well in certain conditions. In this paper, we build upon the mentioned result, working out the correct belief propagation algorithm, which needs to take into account the many-body nature of the constraints present in this problem. This method improves the naive belief propagation approach, at the cost of increased computational effort. We also investigate the emergence of a satisfiable to unsatisfiable "phase transition" as a function of the vertex mean degree, for different ensembles of sparse random graphs in the large size ("thermodynamic") limit.
---
PDF链接:
https://arxiv.org/pdf/1104.4024