Polynomial-time algorithms for multimarginal optimal transport problems with structure

DOI10.1007/s10107-022-01868-7zbMath1518.90048arXiv2008.03006OpenAlexW3047849019WikidataQ114228473 ScholiaQ114228473MaRDI QIDQ6038667

Jason M. Altschuler, Enric Boix-Adserà

Publication date: 2 May 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.03006

zbMATH Keywords

polynomial-time algorithmsmultimarginal optimal transportstructured linear programsimplicit linear programming

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (1)

Low-Rank Tensor Approximations for Solving Multimarginal Optimal Transport Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tensor Decompositions and Applications
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Discrete Wasserstein barycenters: optimal transport for discrete data
• The dual least action problem for an ideal, incompressible fluid
• On the \(n\)-coupling problem
• Matching for teams
• Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness
• Generalized solutions and hydrostatic approximation of the Euler equations
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization.
• Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm
• Hardness results for multimarginal optimal transport problems
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Convolutional wasserstein distances
• Price of Correlations in Stochastic Optimization
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Persistency Model and Its Applications in Choice Modeling
• Barycenters in the Wasserstein Space
• Convex majorization with an application to the length of critical paths
• Probabilistic PERT
• The Complexity of Ferromagnetic Ising with Local Fields
• Numerical methods for matching for teams and Wasserstein barycenters
• The Least Action Principle and the Related Concept of Generalized Flows for Incompressible Perfect Fluids
• Learning Mixtures of Product Distributions over Discrete Domains
• Graphical Models, Exponential Families, and Variational Inference
• Robustness against dependence in PERT: An application of duality and distributions with known marginals
• Computational Complexity of Network Reliability Analysis: An Overview
• Stochastic Bounds on Distributions of Optimal Value Functions with Applications to PERT, Network Flows and Reliability
• Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations
• The Complexity of Enumeration and Reliability Problems
• Polynomial algorithms in linear programming
• Random variables with maximum sums
• Estimates for the Distribution Function of a Sum of Two Random Variables When the Marginal Distributions are Fixed
• Polynomial algorithms for estimating network reliability
• A simple min-cut algorithm
• Combinatorial approaches to Monte Carlo estimation of network lifetime distribution
• Density Functional Theory and Optimal Transportation with Coulomb Cost
• An entropy minimization approach to second-order variational mean-field games
• Multi-Marginal Optimal Transport and Probabilistic Graphical Models
• Extremal Probability Bounds in Combinatorial Optimization
• Wasserstein Barycenters Are NP-Hard to Compute
• Distributionally Robust Linear and Discrete Optimization with Marginals
• A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
• Iterative Bregman Projections for Regularized Transportation Problems
• A Numerical Method to Solve Multi-Marginal Optimal Transport Problems with Coulomb Cost
• Learning with Submodular Functions: A Convex Optimization Perspective
• Treewidth: Structure and Algorithms
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Reliable circuits using less reliable relays
• Computing correlated equilibria in multi-player games

This page was built for publication: Polynomial-time algorithms for multimarginal optimal transport problems with structure