A Practical Markov Chain Monte Carlo Approach to Decision Problems

Timothy Huang and Yuriy Nevmyvaka, Middlebury College, USA

Decision and optimization problems involving graphs arise in many areas of artificial intelligence, including probabilistic networks, robot navigation, and network design. Many such problems are NP-complete; this has necessitated the development of approximation methods, most of which are very complex and highly problemspecific. We propose a straightforward, practical approach to algorithm design based on Markov Chain Monte Carlo (MCMC), a statistical simulation scheme for efficiently sampling from a large (possibly exponential) set, such as the set of feasible solutions to a combinatorial task. This facilitates the development of simple, efficient, and general solutions to whole classes of decision problems. We provide detailed examples showing how this approach can be used for spanning tree problems such as Degree-Constrained Spanning Tree, Maximum Leaf Spanning Tree, and Kth Best Spanning Tree.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.