A faster exact separation algorithm for blossom inequalities
作者： Adam N. Letchford , Gerhard Reinelt , Dirk Oliver Theis
DOI: 10.1007/978-3-540-25960-2_15
关键词: Mathematics 、 Separation algorithm 、 Time complexity 、 Matching (graph theory) 、 Polynomial method 、 Polyhedron 、 Combinatorics
摘要: In 1982, Padberg and Rao gave a polynomial-time separation algorithm for b-matching polyhedra. The current best known implementations of their run in \({\cal O}(|V|^2|E| \log (|V|^2/|E|))\) time when there are no edge capacities, but O}(|V||E|^2 capacities present.
springer.com
sci-hub.st 参考文章(14)
W. Pulleyblank, Jack Edmonds, Facets of I-matching polyhedra Hypergraph Seminar. pp. 214- 242 ,(1974) , 10.1007/BFB0066196
Martin Grötschel, Manfred W. Padberg, On the symmetric travelling salesman problem II: Lifting theorems and facets Mathematical Programming. ,vol. 16, pp. 281- 302 ,(1979) , 10.1007/BF01582117
Martin Grötschel, Olaf Holland, A cutting plane algorithm for minimum perfect 2-matchings Computing. ,vol. 39, pp. 327- 344 ,(1987) , 10.1007/BF02239975
J.P. Secrétan, Der Saccus endolymphaticus bei Entzündungsprozessen ORL. ,vol. 6, pp. 1- 29 ,(1944) , 10.1159/000273299
Manfred Padberg, Giovanni Rinaldi, Facet identification for the symmetric traveling salesman polytope Mathematical Programming. ,vol. 47, pp. 219- 257 ,(1990) , 10.1007/BF01580861
Martin Grötschel, Manfred W. Padberg, On the symmetric travelling salesman problem I: Inequalities Mathematical Programming. ,vol. 16, pp. 265- 280 ,(1979) , 10.1007/BF01582116
Andrew V. Goldberg, Robert E. Tarjan, A new approach to the maximum-flow problem Journal of the ACM. ,vol. 35, pp. 921- 940 ,(1988) , 10.1145/48014.61051
Martin Grötschel, László Lovász, Alexander Schrijver, Geometric Algorithms and Combinatorial Optimization ,(1988)
R. E. Gomory, T. C. Hu, Multi-Terminal Network Flows Journal of The Society for Industrial and Applied Mathematics. ,vol. 9, pp. 551- 570 ,(1961) , 10.1137/0109047
Manfred W. Padberg, M. R. Rao, Odd Minimum Cut-Sets and b-Matchings Mathematics of Operations Research. ,vol. 7, pp. 67- 80 ,(1982) , 10.1287/MOOR.7.1.67