Fetching the paper…
Reading the bibliography…
We study the complexity of approximating the multimarginal optimal transport (MOT) distance, a generalization of the classical optimal transport distance, considered here between $m$ discrete probability distributions supported each on $n$ support points.
On the efficiency of the Sinkhorn and Greenkhorn algorithms and their acceleration for optimal transport
T. Lin, N. Ho, and M. I. Jordan · 1906
Earlier work this paper cites.
On the translocation of masses
L. V. Kantorovich · 1942
Earlier work this paper cites.
Caractérisation des matrices totalement unimodulaires
A. Ghouila-Houri · 1962
Earlier work this paper cites.
A primal method for minimal cost flows with applications to the assignment and transportation problems
M. Klein · 1967
Earlier work this paper cites.
The speed of mean Glivenko-Cantelli convergence
R. M. Dudley · 1969
Earlier work this paper cites.
Theoretical improvements in algorithmic efficiency for network flow problems
J. Edmonds and R. M. Karp · 1972
Earlier work this paper cites.
Reducibility among combinatorial problems
R. M. Karp · 1972
Earlier work this paper cites.
The minimum cost flow problem: a unifying approach to dual algorithms and a new tree-search algorithm
R. Hassin · 1983
Earlier work this paper cites.
A strongly polynomial minimum cost circulation algorithm
É. Tardos · 1985
Earlier work this paper cites.
An o(n2(m+nlogn)logn) min-cost flow algorithm
Z. Galil and É. Tardos · 1988
Earlier work this paper cites.
The least action principle and the related concept of generalized flows for incompressible perfect fluids
Y. Brenier · 1989
Earlier work this paper cites.
Finding minimum-cost circulations by successive approximation
A. V. Goldberg and R. E. Tarjan · 1990
Earlier work this paper cites.
Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
R. Hassin · 1992
Earlier work this paper cites.
A faster strongly polynomial minimum cost flow algorithm
J. B. Orlin · 1993
Earlier work this paper cites.
A polynomial time primal network simplex algorithm for minimum cost flows
J. B. Orlin · 1997
Earlier work this paper cites.
Dynamic trees as search trees via euler tours, applied to the network simplex algorithm
R. E. Tarjan · 1997
Earlier work this paper cites.
Primal-Dual Interior-Point Methods , volume 54
S. J. Wright · 1997
Earlier work this paper cites.
Optimal maps for the multidimensional Monge-Kantorovich problem
W. Gangbo and A. Swiech · 1998
Earlier work this paper cites.
Beyond the flow decomposition barrier
A. V. Goldberg and S. Rao · 1998
Earlier work this paper cites.
Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations
Y. Brenier · 1999
Earlier work this paper cites.
The Theory of Graphs
C. Berge · 2001
Earlier work this paper cites.
Computers and Intractability , volume 29
M. R. Garey and D. S. Johnson · 2002
Earlier work this paper cites.
Combinatorial Optimization: Polyhedra and Efficiency , volume 24
A. Schrijver · 2003
Earlier work this paper cites.
Topics in Optimal Transportation
C. Villani · 2003
Earlier work this paper cites.
An optimal matching problem
I. Ekeland · 2005
Earlier work this paper cites.
Smooth minimization of non-smooth functions
Y. Nesterov · 2005
Earlier work this paper cites.
Strictly correlated electrons in density-functional theory: A general formulation with applications to spherical densities
M. Seidl, P. Gori-Giorgi, and A. Savi · 2007
Earlier work this paper cites.
Generalized solutions and hydrostatic approximation of the Euler equations
Y. Brenier · 2008
Earlier work this paper cites.
Faster approximate lossy generalized flow via interior point algorithms
S. I. Daitch and D. A. Spielman · 2008
Earlier work this paper cites.
On accelerated proximal gradient methods for convex-concave optimization
P. Tseng · 2008
Cited alongside, same era.
Barycenters in the Wasserstein space
M. Agueh and G. Carlier · 2011
Cited alongside, same era.
Nearest neighbor based greedy coordinate descent
I. S. Dhillon, P. K. Ravikumar, and A. Tewari · 2011
Cited alongside, same era.
Optimal-transport formulation of electronic density-functional theory
G. Buttazzo, L. D. Pascale, and P. Gori-Giorgi · 2012
Cited alongside, same era.
Elements of Information Theory
T. M. Cover and J. A. Thomas · 2012
Cited alongside, same era.
Convergence rate analysis of MAP coordinate minimization algorithms
O. Meshi, A. Globerson, and T. S. Jaakkola · 2012
Cited alongside, same era.
Semidual regularized optimal transport
M. Cuturi and G. Peyré · 2018
Later among the works it cites.
Alternating randomized block coordinate descent
J. Diakonikolas and L. Orecchia · 2018
Later among the works it cites.
Unsupervised multi-domain image translation with domain-specific encoders/decoders
L. Hui, X. Li, J. Chen, H. He, and J. Yang · 2018
Later among the works it cites.
Large scale computation of means and clusters for persistence diagrams using optimal transport
T. Lacombe, M. Cuturi, and S. Oudot · 2018
Later among the works it cites.
Accelerating greedy coordinate descent methods
H. Lu, R. Freund, and V. Mirrokni · 2018
Later among the works it cites.
Lectures on Convex Optimization , volume 137
Y. Nesterov · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Efficiency of coordinate descent methods on huge-scale optimization problems
Y. Nesterov · 2012
Cited alongside, same era.
Density functional theory and optimal transportation with Coulomb cost
C. Cotar, G. Friesecke, and C. Klüppelberg · 2013
Cited alongside, same era.
Sinkhorn distances: Lightspeed computation of optimal transport
M. Cuturi · 2013
Cited alongside, same era.
Kantorovich dual solution for strictly correlated electrons in atoms and molecules
C. B. Mendl and L. Lin · 2013
Cited alongside, same era.
Fast computation of Wasserstein barycenters
M. Cuturi and A. Doucet · 2014
Cited alongside, same era.
Robust hedging and martingale optimal transport in continuous time
Y. Dolinsky and M. H. Soner · 2014
Cited alongside, same era.
Scalable Bayes via barycenter in Wasserstein space
S. Srivastava, C. Li, and D. Dunson · 2018
Later among the works it cites.
Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm
J-D. Benamou, G. Carlier, and L. Nenna · 2019
Closest in time.
Multi-marginal Wasserstein GAN
J. Cao, L. Mo, Y. Zhang, K. Jia, C. Shen, and M. Tan · 2019
Closest in time.
Solving linear programs in the current matrix multiplication time
M. B. Cohen, Y. T. Lee, and Z. Song · 2019
Closest in time.
Interior-point methods strike back: Solving the Wasserstein barycenter problem
D. Ge, H. Wang, Z. Xiong, and Y. Ye · 2019
Closest in time.
Sample complexity of Sinkhorn divergences
A. Genevay, L. Chizat, F. Bach, M. Cuturi, and G. Peyré · 2019
Closest in time.
Accelerated alternating minimization, accelerated Sinkhorn’s algorithm and accelerated iterative Bregman projections
S. Guminov, P. Dvurechensky, N. Tupitsa, and A. Gasnikov · 2019
Closest in time.
Attgan: Facial attribute editing by only changing what you want
Z. He, W. Zuo, M. Kan, S. Shan, and X. Chen · 2019
Closest in time.
A direct tilde { \{ O } \} (1/epsilon) iteration parallel algorithm for optimal transport
A. Jambulapati, A. Sidford, and K. Tian · 2019
Closest in time.
On the complexity of approximating Wasserstein barycenters
A. Kroshnin, N. Tupitsa, D. Dvinskikh, P. Dvurechensky, A. Gasnikov, and C. Uribe · 2019
Closest in time.
A graph theoretic additive approximation of optimal transport
N. Lahn, D. Mulchandani, and S. Raghvendra · 2019
Closest in time.
Statistical bounds for entropic optimal transport: Sample complexity and the central limit theorem
G. Mena and J. Niles-Weed · 2019
Closest in time.
Computational Optimal Transport: With Applications to Data Science
G. Peyré and M. Cuturi · 2019
Closest in time.
Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
J. Weed and F. Bach · 2019
Closest in time.
Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces
J. Lei · 2020
Closest in time.
Fixed-support Wasserstein barycenters: Computational hardness and fast algorithm
T. Lin, N. Ho, X. Chen, M. Cuturi, and M. I. Jordan · 2020
Closest in time.
Multi-marginal optimal transport defines a generalized metric
L. Mi and J. Bento · 2020
Closest in time.
On unbalanced optimal transport: An analysis of Sinkhorn algorithm
K. Pham, K. Le, N. Ho, T. Pham, and H. Bui · 2020
Closest in time.
Multimarginal optimal transport by accelerated alternating minimization
N. Tupitsa, P. Dvurechensky, A. Gasnikov, and C. A. Uribe · 2020
Closest in time.
A fast proximal point method for computing exact Wasserstein distance
Y. Xie, X. Wang, R. Wang, and H. Zha · 2020
Closest in time.
Wasserstein barycenters are NP-hard to compute
J. M. Altschuler and E. Boix-Adserà · 2022
Closest in time.
On multimarginal partial optimal transport: Equivalent forms and computational complexity
K. Le, H. Nguyen, K. Nguyen, T. Pham, and N. Ho · 2022
Closest in time.