Blossom V: a new implementation of a minimum cost perfect matching algorithm
By Vladimir Kolmogorov. 2009
490 citations recorded by the source corpus.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Gauthier Gidel
- Simon Lacoste-Julien
- Tony Jebara
- Joseph Francis Fitzsimons
- Georg Martius
- Anselm Paulus
- Joschka Roffe
- Vít Musil
In Computer Networks and Communications
- Joseph Francis Fitzsimons
- Simon Lacoste-Julien
- Georg Martius
- Anselm Paulus
- Joschka Roffe
- Vít Musil
- Nicolas Delfosse
- Tony Jebara
In Algorithms & Complexity
- Joseph Francis Fitzsimons
- Simon Lacoste-Julien
- Georg Martius
- Anselm Paulus
- Joschka Roffe
- Vít Musil
- Nicolas Delfosse
- Tony Jebara
Citations in the corpus
- Frank-Wolfe Algorithms for Saddle Point Problems (2016, methodology): “To solve the perfect matching problem, we used Blossom V by Kolmogorov (2009).”
- Quantum error correction: an introductory guide (2019, methodology): “For surface codes, a technique known as minimum weight perfect matching (MWPM) can be used for decoding, which works by identifying error chains between positive syndrome measurements [56,57].”
- Almost-linear time decoding algorithm for topological codes (2017, background): “Minimum weight perfect matching (MWPM) decoder [19] is currently the most standard decoder for topological codes, and has a worst case complexity of between O(n3) and O(n7) depending on the implementation [45].”
- Differentiation of Blackbox Combinatorial Solvers (2019, methodology): “In experiments, we train architectures that contain unmodified implementations of the following efficient combinatorial algorithms: general-purpose mixed-integer programming solver Gurobi [18], state-of-the-art C implementation of MIN-COST-PERFECT-MATCHING algorithm – Blossom V [24] and Dijkstra’s a”
- Freely Scalable Quantum Technologies using Cells of 5-to-50 Qubits with Very Lossy and Noisy Photonic Links (2014, methodology): “Decoding is performed using Kolgomorov’s Blossom V implementation of Edmond’s minimum weight matching algorithm [34, 35] to generate a ‘perfect’ matching be-tween stabilizer violations.”
- Sparse Blossom: correcting a million errors per core second with minimum-weight matching (2023, unknown): “See [Kol09] for a more detailed discussion and comparison of these different strategies.”