NeurIPS 2017poster6 citations
Min-Max Propagation
Christopher Srinivasa, Inmar Givoni, Siamak Ravanbakhsh, Brendan J. Frey
Abstract
We study the application of min-max propagation, a variation of belief propagation, for approximate min-max inference in factor graphs. We show that for “any” high-order function that can be minimized in O(ω), the min-max message update can be obtained using an efficient O(K(ω + log(K)) procedure, where K is the number of variables. We demonstrate how this generic procedure, in combination with efficient updates for a family of high-order constraints, enables the application of min-max propagation to efficiently approximate the NP-hard problem of makespan minimization, which seeks to distribute a set of tasks on machines, such that the worst case load is minimized.
BibTeX
@inproceedings{NIPS2017_327708dd,
author = {Srinivasa, Christopher and Givoni, Inmar and Ravanbakhsh, Siamak and Frey, Brendan J},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Min-Max Propagation},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/327708dd10d68b1361ad3addbaca01f2-Paper.pdf},
volume = {30},
year = {2017}
}