Minmax Propagation. Ravanbakhsh, S., Srinivasa, C., & Frey, B. In 2017. pdf coming soon!
abstract   bibtex   
"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 functions that can be minimized in O(m), the min-max message update can be obtained using an efficient O(K (m + 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."
@InProceedings{chris_minmax_prop,
  author={Ravanbakhsh, Siamak and Srinivasa, Christopher and Frey, Brendan},
  title={Minmax Propagation},
  journal = {Proceedings of the Neural Information Processing Systems (NIPS)},
  shortbooktitle={NIPS},
  location= { Long Beach , CA},
  year = {2017},
  order={2},
  year={2017},
Bibbase_Note={<font> pdf coming soon!</font>},  
  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 functions that can be minimized in O(m), the min-max message update can be obtained using an efficient O(K (m + 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."},
}

Downloads: 0