...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Analysis of the Min-Sum Algorithm for Packing and Covering Problems via Linear Programming
【24h】

Analysis of the Min-Sum Algorithm for Packing and Covering Problems via Linear Programming

机译：线性规划的最小包装和覆盖问题求和算法分析

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Message-passing algorithms based on belief-propagation (BP) are successfully used in many applications, including decoding error correcting codes and solving constraint satisfaction and inference problems. The BP-based algorithms operate over graph representations, called factor graphs, that are used to model the input. Although in many cases, the BP-based algorithms exhibit impressive empirical results, not much has been proved when the factor graphs have cycles. This paper deals with packing and covering integer programs in which the constraint matrix is zero-one, the constraint vector is integral, and the variables are subject to box constraints. We study the performance of the min-sum algorithm when applied to the corresponding factor graph models of packing and covering linear programmings (LPs). We compare the solutions computed by the min-sum algorithm for packing and covering problems to the optimal solutions of the corresponding LP relaxations. In particular, we prove that if the LP has an optimal fractional solution, then for each fractional component, the min-sum algorithm either computes multiple solutions or the solution oscillates below and above the fraction. This implies that the min-sum algorithm computes the optimal integral solution only if the LP has a unique optimal solution that is integral. The converse is not true in general. For a special case of packing and covering problems, we prove that if the LP has a unique optimal solution that is integral and on the boundary of the box constraints, then the min-sum algorithm computes the optimal solution in pseudopolynomial time. Our results unify and extend recent results for the maximum weight matching problem and for the maximum weight independent set problem.
机译：基于置信传播（BP）的消息传递算法已成功用于许多应用中，包括解码纠错码以及解决约束满足和推理问题。基于BP的算法对称为因子图的图形表示进行操作，这些图形表示用于对输入进行建模。尽管在许多情况下，基于BP的算法显示出令人印象深刻的经验结果，但是当因子图具有循环时，并没有得到太多证明。本文处理和覆盖整数程序，其中约束矩阵为零一，约束向量为整数，变量受盒约束。我们研究了最小和算法应用于打包和覆盖线性规划（LP）的相应因子图模型时的性能。我们将最小和算法计算的用于打包和覆盖问题的解与相应的LP松弛的最优解进行比较。特别是，我们证明了，如果LP具有最优的分数解，则对于每个分数分量，最小总和算法要么计算多个解，要么溶液在分数上下浮动。这意味着最小和算法仅在LP具有积分的唯一最优解时才计算最优积分解。相反，通常情况并非如此。对于打包和覆盖问题的特殊情况，我们证明，如果LP具有唯一的最优解，且该解是整数且位于盒约束的边界上，则min-sum算法将在伪多项式时间内计算出最优解。我们的结果统一和扩展了最大权重匹配问题和最大权重独立集问题的最新结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号