Timezone: »

 
Poster
Min-Max Propagation
Christopher Srinivasa · Inmar Givoni · Siamak Ravanbakhsh · Brendan J Frey

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #175
in Posters Wed »

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.

Keywords: Combinatorial Optimization · Graphical Models · Belief Propagation · Computational Complexity
[ Paper]  [ Poster] 

Author Information

Christopher Srinivasa (University of Toronto/Borealis AI)
Inmar Givoni (University of Toronto)
Siamak Ravanbakhsh (CMU/UBC)
Brendan J Frey (Deep Genomics, Vector Institute, Univ. Toronto)

Brendan Frey is Co-Founder and CEO of Deep Genomics, a Co-Founder of the Vector Institute for Artificial Intelligence, and a Professor of Engineering and Medicine at the University of Toronto. He is internationally recognized as a leader in machine learning and in genome biology and his group has published over a dozen papers on these topics in Science, Nature and Cell. His work on using deep learning to identify protein-DNA interactions was recently highlighted on the front cover Nature Biotechnology (2015), while his work on deep learning dates back to an early paper on what are now called variational autoencoders (Science 1995). He is a Fellow of the Royal Society of Canada, a Fellow of the Institute for Electrical and Electronic Engineers, and a Fellow of the American Association for the Advancement of Science. He has consulted for several industrial research and development laboratories in Canada, the United States and England, and has served on the Technical Advisory Board of Microsoft Research.

More from the Same Authors