Balancing Asymmetry in Max-sum Using Split Constraint Factor Graphs
Balancing Asymmetry in Max-sum Using Split Constraint Factor Graphs
复制标题
使用分割约束因子图平衡最大和中的不对称性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Zivan
中科院分区：
文献类型：
--
作者：
Liel Cohen;R. Zivan
Max-sum 是置信传播的一个版本，用于解决 DCOP。对于树结构问题，Max-sum 在线性时间内收敛到最优解。当表示问题的约束图包含多个循环时，Max-sum 可能无法收敛并探索低质量的解决方案。阻尼是一种增加最大和收敛机会的方法。最近发现，阻尼最大和 (DMS) 与随时框架相结合可以为 DCOP 生成高质量的解决方案。
Max-sum is a version of Belief Propagation, used for solving DCOPs. On tree-structured problems, Max-sum converges to the optimal solution in linear time. When the constraint graph representing the problem includes multiple cycles, Max-sum might not converge and explore low quality solutions. Damping is a method that increases the chances that Max-sum will converge. Damped Max-sum (DMS) was recently found to produce high quality solutions for DCOP when combined with an anytime framework.