Min-Max Propagation

Christopher Srinivasa, Inmar Givoni, Siamak Ravanbakhsh, Brendan J. Frey

NeurIPS 2017 pp. 5565-5573

/neurips/2017/srinivasa2017neurips-minmax/

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.

PDF NeurIPS Semantic Scholar

Cite

Text

Srinivasa et al. "Min-Max Propagation." Neural Information Processing Systems, 2017.

Markdown

[Srinivasa et al. "Min-Max Propagation." Neural Information Processing Systems, 2017.](https://mlanthology.org/neurips/2017/srinivasa2017neurips-minmax/)

BibTeX

@inproceedings{srinivasa2017neurips-minmax,
  title     = {{Min-Max Propagation}},
  author    = {Srinivasa, Christopher and Givoni, Inmar and Ravanbakhsh, Siamak and Frey, Brendan J.},
  booktitle = {Neural Information Processing Systems},
  year      = {2017},
  pages     = {5565-5573},
  url       = {https://mlanthology.org/neurips/2017/srinivasa2017neurips-minmax/}
}