Fetching the paper…
Reading the bibliography…
We investigate the problem of pairwise multi-marginal optimal transport, that is, given a collection of probability distributions $\{P_\alpha\}$ on a Polish space $\mathcal{X}$, to find a coupling $\{X_\alpha\}$, $X_\alpha\sim P_\alpha$, such that $\mathbf{E}[c(X_\alpha,X_\beta)]\le r\inf_{X\sim P_\alpha,Y\sim P_\beta}\mathbf{E}[c(X,Y)]$ for all $\alpha,\beta$, where $c$ is a cost function and $r\ge1$.
L. V. Kantorovich, “On the translocation of masses,” in Dokl. Akad. Nauk. USSR (NS) , vol. 37, 1942, pp. 199–201
1942
Earlier work this paper cites.
J. Bretagnolle, D. Dacunha Castelle, and J.-L. Krivine, “Lois stables et espaces L p L^{p} ,” in Annales de l’IHP Probabilités et statistiques , vol. 2, no. 3, 1966, pp. 231–259
1966
Earlier work this paper cites.
R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of computer computations . Springer, 1972, pp. 85–103
1972
Earlier work this paper cites.
P. Assouad, “Plongements lipschitziens dans ℝ n \mathbb{R}^{n} ,” Bulletin de la Société Mathématique de France , vol. 111, pp. 429–448, 1983
1983
Earlier work this paper cites.
H. G. Kellerer, “Duality theorems for marginal problems,” Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete , vol. 67, no. 4, pp. 399–432, 1984
1984
Earlier work this paper cites.
J. Bourgain, “On Lipschitz embedding of finite metric spaces in Hilbert space,” Israel Journal of Mathematics , vol. 52, no. 1-2, pp. 46–52, 1985
1985
Earlier work this paper cites.
S. Peleg, M. Werman, and H. Rom, “A unified approach to the change of resolution: Space and gray-level,” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 11, no. 7, pp. 739–742, 1989
1989
Earlier work this paper cites.
R. M. Karp, “A 2 k 2k -competitive algorithm for the circle,” Manuscript , August 1989
1989
Earlier work this paper cites.
S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica . Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1991
1991
Earlier work this paper cites.
B. Bollobás and I. Leader, “Edge-isoperimetric inequalities in the grid,” Combinatorica , vol. 11, no. 4, pp. 299–314, 1991
1991
Earlier work this paper cites.
J. F. C. Kingman, Poisson Processes . Oxford University Press, 1993
1993
Earlier work this paper cites.
N. Linial, E. London, and Y. Rabinovich, “The geometry of graphs and some of its algorithmic applications,” Combinatorica , vol. 15, no. 2, pp. 215–245, 1995
1995
Earlier work this paper cites.
N. Alon, R. M. Karp, D. Peleg, and D. West, “A graph-theoretic game and its application to the k k -server problem,” SIAM Journal on Computing , vol. 24, no. 1, pp. 78–100, 1995
1995
Earlier work this paper cites.
Y. Bartal, “Probabilistic approximation of metric spaces and its algorithmic applications,” in Proceedings of 37th Conference on Foundations of Computer Science . IEEE, 1996, pp. 184–193
1996
Earlier work this paper cites.
C. Rousseau and O. Ruehr, “Problems and solutions. subsection: The volume of the intersection of a cube and a ball in N-space. two solutions by Bernd Tibken and Denis Constales,” SIAM Review , vol. 39, pp. 779–786, 1997
1997
Earlier work this paper cites.
W. Gangbo and A. Święch, “Optimal maps for the multidimensional Monge-Kantorovich problem,” Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , vol. 51, no. 1, pp. 23–45, 1998
1998
Earlier work this paper cites.
S. T. Rachev and L. Rüschendorf, Mass Transportation Problems: Volume I: Theory . Springer Science & Business Media, 1998, vol. 1
1998
Earlier work this paper cites.
Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” in Proceedings of the Seventh IEEE International Conference on Computer Vision , vol. 1. IEEE, 1999, pp. 377–384
1999
Earlier work this paper cites.
D. Bertsimas, C. Teo, and R. Vohra, “On dependent randomized rounding algorithms,” Operations Research Letters , vol. 24, no. 3, pp. 105–114, 1999
1999
Cited alongside, same era.
D. Burago, I. D. Burago, Y. Burago, S. A. Ivanov, and S. Ivanov, A course in metric geometry . American Mathematical Soc., 2001, vol. 33
2001
Cited alongside, same era.
——, “Fast approximate energy minimization via graph cuts,” IEEE Transactions on pattern analysis and machine intelligence , vol. 23, no. 11, pp. 1222–1239, 2001
2001
Cited alongside, same era.
H. Heinich, “Problème de monge pour n probabilités,” Comptes Rendus Mathematique , vol. 334, no. 9, pp. 793–795, 2002
2002
Cited alongside, same era.
M. S. Charikar, “Similarity estimation techniques from rounding algorithms,” in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing . ACM, 2002, pp. 380–388
A. Andoni, K. Do Ba, P. Indyk, and D. Woodruff, “Efficient sketches for earth-mover distance, with applications,” in 2009 50th Annual IEEE Symposium on Foundations of Computer Science . IEEE, 2009, pp. 324–330
2009
Later among the works it cites.
M. Iwasa, H. Saito, and T. Matsui, “Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems,” Discrete Applied Mathematics , vol. 157, no. 9, pp. 2078–2088, 2009
2009
Later among the works it cites.
G. Carlier and I. Ekeland, “Matching for teams,” Economic theory , vol. 42, no. 2, pp. 397–418, 2010
2010
Later among the works it cites.
P.-A. Chiappori, R. J. McCann, and L. P. Nesheim, “Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness,” Economic Theory , vol. 42, no. 2, pp. 317–354, 2010
2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2002
Cited alongside, same era.
J. Kleinberg and E. Tardos, “Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields,” Journal of the ACM (JACM) , vol. 49, no. 5, pp. 616–639, 2002
2002
Cited alongside, same era.
F. Barthe and A. Naor, “Hyperplane projections of the unit ball of ℓ p n \ell_{p}^{n} ,” Discrete & Computational Geometry , vol. 27, no. 2, pp. 215–226, 2002
2002
Cited alongside, same era.
J. Jost, Riemannian Geometry and Geometric Analysis . Berlin Heidelberg: Springer-Verlag, 2002
2002
Cited alongside, same era.
G. Carlier, “On a class of multidimensional optimal transportation problems,” Journal of convex analysis , vol. 10, no. 2, pp. 517–530, 2003
2003
Cited alongside, same era.
P. Indyk and N. Thaper, “Fast image retrieval via embeddings,” in 3rd international workshop on statistical and computational theories of vision , 2003, pp. 1–15
2003
Cited alongside, same era.
Q. Lv, M. Charikar, and K. Li, “Image similarity search with compact data structures,” in Proceedings of the thirteenth ACM international conference on Information and knowledge management . ACM, 2004, pp. 208–217
2004
Cited alongside, same era.
A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, and É. Tardos, “Approximate classification via earthmover metrics,” in Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms . Society for Industrial and Applied Mathematics, 2004, pp. 1079–1087
2004
Cited alongside, same era.
B. Pass, “Uniqueness and Monge solutions in the multimarginal optimal transportation problem,” SIAM Journal on Mathematical Analysis , vol. 43, no. 6, pp. 2758–2775, 2011
2011
Later among the works it cites.
——, “On the local structure of optimal measures in the multi-marginal optimal transportation problem,” Calculus of Variations and Partial Differential Equations , vol. 43, no. 3-4, pp. 529–536, 2012
2012
Later among the works it cites.
2012
Later among the works it cites.
F. Keshavarz-Kohjerdi, A. Bagheri, and A. Asgharian-Sardroud, “A linear-time algorithm for the longest path problem in rectangular grid graphs,” Discrete Applied Mathematics , vol. 160, no. 3, pp. 210–217, 2012
2012
Later among the works it cites.
A. Bačkurs and P. Indyk, “Better embeddings for planar earth-mover distance over sparse sets,” in Proceedings of the thirtieth annual symposium on Computational geometry . ACM, 2014, p. 280
2014
Later among the works it cites.
B. R. Kloeckner, “A geometric study of Wasserstein spaces: ultrametrics,” Mathematika , vol. 61, no. 1, pp. 162–178, 2015
2015
Later among the works it cites.
P. Petersen, Riemannian Geometry . Springer, 2016
2016
Later among the works it cites.
G. Last and M. Penrose, Lectures on the Poisson process . Cambridge University Press, 2017, vol. 7
2017
Later among the works it cites.
C. T. Li and A. El Gamal, “Strong functional representation lemma and applications to coding theorems,” IEEE Transactions on Information Theory , vol. 64, no. 11, pp. 6967–6978, Nov 2018
2018
Later among the works it cites.
2018
Later among the works it cites.
W. Leeb, “Approximating snowflake metrics by trees,” Applied and Computational Harmonic Analysis , vol. 45, no. 2, pp. 405–424, 2018
2018
Later among the works it cites.
R. Hühnerbein, F. Savarino, F. Åström, and C. Schnörr, “Image labeling based on graphical models using Wasserstein messages and geometric assignment,” SIAM Journal on Imaging Sciences , vol. 11, no. 2, pp. 1317–1362, 2018
2018
Later among the works it cites.
A. Andoni, A. Naor, and O. Neiman, “Snowflake universality of Wasserstein spaces,” in Annales Scientifiques de l’Ecole Normale Superieure , vol. 51, no. 3. Societe Mathematique de France, 2018, pp. 657–700
2018
Later among the works it cites.