2011/02/28 by Julie Delon, Julien Salomon, Andreĭ Sobolevskiĭ +1 · 7 citations
Mathematics · #Algorithm #Combinatorics #Geometric Analysis and Curvature Flows #Geometry #Geometry and complex manifolds #Graph #Line (geometry) #Line graph #Line segment #Matching (statistics) #Mathematics #Minimum weight #Point processes and geometric inequalities #Real line #Recursion (computer science) #Statistics #math.OC
paper · pdf · doi:10.1007/s10958-012-0714-6
published in Journal of Mathematical Sciences 181(6), 782-791 (Springer Science+Business Media) · 13 pages, figures in TiKZ, uses xcolor package; introduction and the concluding section have been expanded
arxiv created 2011/03/26 · openalex publication_date 2012/02/29 · arxiv updated 2012/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Consider a real line equipped with a (not necessarily intrinsic) distance. We deal with the minimum-weight perfect matching problem for a complete graph whose points are located on the line and whose edges have weights equal to distances along the line. This problem is closely related to one-dimensional Monge-Kantorovich trasnport optimization. The main result of the present note is a "bottom-up" recursion relation for weights of partial minimum-weight matchings.