Min-Max Problems on Factor Graphs
Siamak Ravanbakhsh, Christopher Srinivasa, Brendan J. Frey, Russell Greiner · 2014
We study the min-max problem in factor graphs, which seeks the assignment that minimizes the maximum value over all factors. We reduce this problem to both min-sum and sum-product infer-ence, and focus on the later. In this approach the min-max inference problem is reduced to a sequence of Constraint Satisfaction Problems (CSP), which allows us to solve the problem by sampling 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), asymmetric K-center clustering problem, K-packing and the bottleneck traveling salesman problem. Further-more, we theoretically relate the min-max reduc-tions and several NP hard decision problems such as clique cover, set-cover, maximum clique and Hamiltonian cycle, therefore also providing mes-sage passing solutions for these problems. Ex-perimental results suggest that message passing often provides near optimal min-max solutions for moderate size instances. 1.