Abstract
H. Xu, S. Kumar and S. Koenig. A New Solver for the Minimum Weighted Vertex Cover Problem. In International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR), pages 392-405, 2016.Abstract: Given a vertex-weighted graph G = (V,E), the minimum weighted vertex cover (MWVC) problem is to choose a subset of vertices with minimum total weight such that every edge in the graph has at least one of its endpoints chosen. While there are good solvers for the unweighted version of this NP-hard problem, the weighted version - i.e., the MWVC problem - remains understudied despite its common occurrence in many areas of AI - like combinatorial auctions, weighted constraint satisfaction, and probabilistic reasoning. In this paper, we present a new solver for the MWVC problem based on a novel reformulation to a series of SAT instances using a primal-dual approximation algorithm as a starting point. We show that our SAT-based MWVC solver (SBMS) significantly outperforms other methods.
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.