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 = {Ravanbakhsh, Siamak and Srinivasa, Christopher and Frey, Brendan and Greiner, Russell}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1035--1043}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, 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 = {https://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 %P 1035--1043 %U https://proceedings.mlr.press/v32/ravanbakhsh14.html %V 32 %N 2 %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 DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-ravanbakhsh14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1035 EP - 1043 L1 - http://proceedings.mlr.press/v32/ravanbakhsh14.pdf UR - https://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 Proceedings of Machine Learning Research 32(2):1035-1043 Available from https://proceedings.mlr.press/v32/ravanbakhsh14.html.

Related Material