Discrete Optimal Transport with Independent Marginals is #P-Hard
From MaRDI portal
Publication:6155882
DOI10.1137/22m1482044zbMath1519.90112arXiv2203.01161OpenAlexW4378977931MaRDI QIDQ6155882
Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, Karthik Natarajan, Bahar Taşkesen
Publication date: 7 June 2023
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2203.01161
Convex programming (90C25) Linear programming (90C05) Dynamic programming (90C39) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computational Optimal Transport: With Applications to Data Science
- A comment on ``Computational complexity of stochastic programming problems
- The complexity of computing the permanent
- Erratum to: ``Computational complexity of stochastic programming problems
- A new polynomial-time algorithm for linear programming
- Auction algorithms for network flow problems: A tutorial introduction
- Geometric algorithms and combinatorial optimization.
- A polynomial time primal network simplex algorithm for minimum cost flows
- Convex histogram-based joint image segmentation with regularized optimal transport cost
- Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
- The earth mover's distance as a metric for image retrieval
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
- Hardness results for multimarginal optimal transport problems
- Wasserstein distance to independence models
- Computational complexity of stochastic programming problems
- Convolutional wasserstein distances
- A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
- Quadratically Regularized Optimal Transport on Graphs
- Wasserstein Loss for Image Synthesis and Restoration
- Approximate counting by dynamic programming
- The Complexity of Enumeration and Reliability Problems
- A new algorithm for the assignment problem
- Polar factorization and monotone rearrangement of vector‐valued functions
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
- Linear Programming
- Earth mover's distances on discrete surfaces
- Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
- Worst-Case Expected Shortfall with Univariate and Bivariate Marginals
- Wasserstein Barycenters Are NP-Hard to Compute
- Lectures on Stochastic Programming: Modeling and Theory, Third Edition
- Regularized Discrete Optimal Transport
- Quantifying Distributional Model Risk via Optimal Transport
- Iterative Bregman Projections for Regularized Transportation Problems
- An FPTAS for #Knapsack and Related Counting Problems
- Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
- Optimal Transport
- Semi-discrete optimal transport: hardness, regularization and numerical solution
This page was built for publication: Discrete Optimal Transport with Independent Marginals is #P-Hard
