Min-Max Problems on Factor Graphs

Siamak Ravanbakhsh, Christopher Srinivasa, Brendan Frey, Russell Greiner
; Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1035-1043, 2014.

Abstract

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 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v32-ravanbakhsh14, title = {Min-Max Problems on Factor Graphs}, author = {Siamak Ravanbakhsh and Christopher Srinivasa and Brendan Frey and Russell Greiner}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1035--1043}, year = {2014}, editor = {Eric P. Xing and Tony Jebara}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/ravanbakhsh14.pdf}, url = {http://proceedings.mlr.press/v32/ravanbakhsh14.html}, abstract = {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 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.} }
Endnote
%0 Conference Paper %T Min-Max Problems on Factor Graphs %A Siamak Ravanbakhsh %A Christopher Srinivasa %A Brendan Frey %A Russell Greiner %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-ravanbakhsh14 %I PMLR %J Proceedings of Machine Learning Research %P 1035--1043 %U http://proceedings.mlr.press %V 32 %N 2 %W PMLR %X 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 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.
RIS
TY - CPAPER TI - Min-Max Problems on Factor Graphs AU - Siamak Ravanbakhsh AU - Christopher Srinivasa AU - Brendan Frey AU - Russell Greiner BT - Proceedings of the 31st International Conference on Machine Learning PY - 2014/01/27 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-ravanbakhsh14 PB - PMLR SP - 1035 DP - PMLR EP - 1043 L1 - http://proceedings.mlr.press/v32/ravanbakhsh14.pdf UR - http://proceedings.mlr.press/v32/ravanbakhsh14.html AB - 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 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. ER -
APA
Ravanbakhsh, S., Srinivasa, C., Frey, B. & Greiner, R.. (2014). Min-Max Problems on Factor Graphs. Proceedings of the 31st International Conference on Machine Learning, in PMLR 32(2):1035-1043

Related Material