Geodesic
Minimum-weight perfect matching for non-intrinsic distances on the line
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XX, Tome 390 (2011), pp. 52-68 
J. Delon; J. Salomon; A. Sobolevski. Minimum-weight perfect matching for non-intrinsic distances on the line. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XX, Tome 390 (2011), pp. 52-68. http://geodesic.mathdoc.fr/item/ZNSL_2011_390_a1/
@article{ZNSL_2011_390_a1,
     author = {J. Delon and J. Salomon and A. Sobolevski},
     title = {Minimum-weight perfect matching for non-intrinsic distances on the line},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {52--68},
     year = {2011},
     volume = {390},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2011_390_a1/}
}
TY  - JOUR
AU  - J. Delon
AU  - J. Salomon
AU  - A. Sobolevski
TI  - Minimum-weight perfect matching for non-intrinsic distances on the line
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2011
SP  - 52
EP  - 68
VL  - 390
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2011_390_a1/
LA  - en
ID  - ZNSL_2011_390_a1
ER  - 
%0 Journal Article
%A J. Delon
%A J. Salomon
%A A. Sobolevski
%T Minimum-weight perfect matching for non-intrinsic distances on the line
%J Zapiski Nauchnykh Seminarov POMI
%D 2011
%P 52-68
%V 390
%U http://geodesic.mathdoc.fr/item/ZNSL_2011_390_a1/
%G en
%F ZNSL_2011_390_a1

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

We consider a minimum-weight perfect matching problem on the line and establish a “bottom-up” recursion relation for weights of partial minimum-weight matchings.

[1] A. Aggarwal, A. Bar-Noy, S. Khuller, D. Kravets, B. Schieber, “Efficient minimum cost matching using quadrangle inequality”, J. Algorithms, 19:1 (1995), 116–143 | DOI | MR | Zbl

[2] D. Burago, Y. Burago, S. Ivanov, A Course in Metric Geometry, Graduate Studies in Mathematics, 33, AMS, Providence, Rhode Island, 2001 | MR | Zbl

[3] W. Cook, A. Rohe, “Computing minimum-weight perfect matching”, INFORMS Journal on Computing, 11:2 (1999), 138–148 | DOI | MR | Zbl

[4] J. Delon, J. Salomon, A. Sobolevski, “Local matching indicators for concave transport costs”, C. R. Acad. Sci. Paris Série I Math., 348:15–16 (2010), 901–905 | DOI | MR | Zbl

[5] J. Delon, J. Salomon, A. Sobolevski, Local matching indicators for transport problems with concave costs, in preparation, 2011 | MR

[6] J. Edmonds, “Maximum matching and a polyhedron with $0,1$-vertices”, Journal of Research of the National Bureau of Standards Sect. B, 69 (1965), 125–130 | DOI | MR | Zbl

[7] J. Edmonds, “Paths, trees and flowers”, Canadian Journal of Mathematics, 17 (1965), 449–467 | DOI | MR | Zbl

[8] J. Heinonen, Lectures on Analysis in Metric Spaces, Universitext, Springer-Verlag, 2001 | DOI | MR | Zbl

[9] R. M. Karp, S. Y. R. Li, “Two special cases of the assignment problem”, Discrete Mathematics, 13 (1975), 129–142 | DOI | MR | Zbl

[10] R. J. McCann, “Exact solutions to the transprtation problem on the line”, Proc. R. Soc. A: Math., Phys. and End. Sci., 455 (1989), 1341–1380 | DOI | MR

[11] M. Werman, S. Peleg, R. Melter, T. Y. Kong, “Bipartite graph matching for points on a line or a circle”, J. Algorithm, 7:2 (1986), 277–284 | DOI | MR | Zbl