A detailed introduction to a minimum-cost perfect matching algorithm based on linear programming

被引：0
作者：
Cheung, Kevin K. H. [1 ]
Governor, Kyel [2 ]
机构：
[1] Carleton Univ, 1125 Colonel By Dr, Ottawa, ON K1S 5B6, Canada
[2] Univ Chicago, 5801 S Ellis Ave, Chicago, IL 60637 USA
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2023年 / 45卷 / 03期
关键词：
Perfect matching; Uniqueness; Perturbation; Linear programming;
D O I：
10.1007/s10878-023-00998-8
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Full technical details for a slightly simplified version of the minimum weight perfect matching via blossom belief propagation by Ahn, Park, Chertkov and Shin (in Advances in neural information processing systems, vol 28, Curran Associates, Inc., 2015) are provided. An example showing the necessity of a certain uniqueness assumption is given. An alternative to perturbing the edge weights to ensure the uniqueness assumption is satisfied is suggested.
引用
收藏
页数：27
相关论文
共 9 条
  • [1] Ahn SS, 2015, ADV NEURAL INFORM PR
  • [2] The Cutting Plane Method is Polynomial for Perfect Matchings
    Chandrasekaran, Karthekeyan
    Vegh, Laszlo A.
    Vempala, Santosh S.
    [J]. MATHEMATICS OF OPERATIONS RESEARCH, 2016, 41 (01) : 23 - 48
  • [3] Chen AmberQ, 2020, OPEN J MATH OPTIM, V1, P2, DOI [10.5802/ojmo.2, DOI 10.5802/OJMO.2]
  • [4] Cho I, 2015, PROCEEDINGS 2015 IEEE INTERNATIONAL CONFERENCE ON BIG DATA, P24, DOI 10.1109/BigData.2015.7363737
  • [5] Computing minimum-weight perfect matchings
    Cook, W
    Rohe, A
    [J]. INFORMS JOURNAL ON COMPUTING, 1999, 11 (02) : 138 - 148
  • [6] Cook W., 1998, COMBINATORIAL OPTIMI, p9780471558941
  • [7] PATHS TREES AND FLOWERS
    EDMONDS, J
    [J]. CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03): : 449 - &
  • [8] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES
    EDMONDS, J
    [J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2): : 125 - +
  • [9] Blossom V: a new implementation of a minimum cost perfect matching algorithm
    Kolmogorov, Vladimir
    [J]. MATHEMATICAL PROGRAMMING COMPUTATION, 2009, 1 (01) : 43 - 67
1