Abstract
M. Nakajima, H. Xu, S. Koenig and S. Kumar. Towards Understanding the Min-Sum Message Passing Algorithm for the Minimum Weighted Vertex Cover Problem: An Analytical Approach. In International Symposium on Artificial Intelligence and Mathematics (ISAIM), 2018.Abstract: Given a vertex-weighted undirected graph G=(V,E,w), the minimum weighted vertex cover (MWVC) problem is to find a subset of vertices with minimum total weight such that every edge in the graph has at least one of its endpoints in it. The MWVC problem and its amenability to the min-sum message passing (MSMP) algorithm remain understudied despite the common occurrence of the MWVC problem and the common use of the MSMP algorithm in many areas of AI. In this paper, we first develop the MSMP algorithm for the MWVC problem that can be viewed as a generalization of the warning propagation algorithm. We then study properties of the MSMP algorithm for the MWVC problem on a special class of graphs, namely single loops. We compare our analytical results with experimental observations and argue that: (a) Our analytical framework is powerful in accurately predicting the behavior of the MSMP algorithm on the MWVC problem, and (b) for a given combinatorial optimization problem, it may be more effective to apply the MSMP algorithm on the MWVC problem that is equivalent to the given problem, instead of applying the MSMP algorithm on the given problem directly.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.