Blossom algorithm

Blossom algorithm

MAP Estimation: Linear Programming Relaxation and Message-Passing Algorithms

Published in Marloes Maathuis, Mathias Drton, Steffen Lauritzen, Martin Wainwright, Handbook of Graphical Models, 2018

Ofer Meshi, Alexander G. Schwing

It is important to note that although the LP relaxations are tight in the above cases, usage of general LP solvers is often not the most efficient way to tackle these problems. Due to their particular structure, specialized algorithms have been designed to find the MAP solutions in these cases. For tree-structured graphs the max-product algorithm is a dynamic programming approach that can compute the MAP solution in linear time [51], see Section 6.6; for supermodular potentials, the MAP solution can be computed by solving a min-cut/max-flow problem on a properly constructed graph, with cost that is cubic in the number of variables [17]; and for maximum weight matching problems, one can obtain a MAP solution for general graphs (not necessarily bipartite) in polynomial time using Edmond’s blossom algorithm [13].

Sparktope: linear programs from algorithms

View Article

Journal Information

Published in Optimization Methods and Software, 2022

David Avis, David Bremner

For a given integer n we will give an upper bound on the number of steps taken in order to reach a return statement. Referring to the source code mm.spk we see that the program is divided into two phases to reduce the number of constraints produced. phaseinit handles initialization and is executed once whereas phasemain performs the blossom algorithm.

Explore chapters and articles related to this topic

MAP Estimation: Linear Programming Relaxation and Message-Passing Algorithms

Sparktope: linear programs from algorithms