Min-Max Problems on Factor-Graphs
- Siamak Ravanbakhsh, Dept of Computing Science, University of Alberta
- Russ Greiner, Dept of Computing Science; PI of AICML
- Brendan Frey
- Christopher Srinivasa
which seeks the assignment that minimizes the maximum value over all factors. We reduce this problem to both min-sum and sum-product inference, and focus on the later. This approach reduces the min-max inference problem to a sequence of constraint satisfaction problems (CSPs) which allows us to sample from a uniform distribution over the set of solutions. We demonstrate how this scheme provides a message passing solution to several NP-hard combinatorial problems, such as min-max clustering (a.k.a. K-clustering), the asymmetric K-center problem, K-packing and the bottleneck traveling salesman problem. Furthermore we theoretically relate the min-max reductions to several NP hard decision problems, such as clique cover, set-cover, maximum clique and Hamiltonian cycle, therefore also providing message passing solutions for these problems. Experimental results suggest that message passing often provides near optimal min-max solutions for moderate size instances.
Citation
S. Ravanbakhsh, R. Greiner, B. Frey, C. Srinivasa. "Min-Max Problems on Factor-Graphs". International Conference on Machine Learning (ICML), pp 1035-1043, June 2014.| Keywords: | probabilistic graphical models, factor graphs, efficient inference |
| Category: | In Conference |
| Web Links: | PMLR |
BibTeX
@incollection{Ravanbakhsh+al:ICML14,
author = {Siamak Ravanbakhsh and Russ Greiner and Brendan Frey and
Christopher Srinivasa},
title = {Min-Max Problems on Factor-Graphs},
Pages = {1035-1043},
booktitle = {International Conference on Machine Learning (ICML)},
year = 2014,
}Last Updated: March 12, 2020Submitted by Sabina P
