Poster
Min-Max Propagation
Christopher Srinivasa · Inmar Givoni · Siamak Ravanbakhsh · Brendan J Frey
Pacific Ballroom #175
Keywords: [ Computational Complexity ] [ Belief Propagation ] [ Graphical Models ] [ Combinatorial Optimization ]
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.
Live content is unavailable. Log in and register to view live content