Research map / Learning theory and algorithms / Optimal transport
A Grid Efficient Transport Optimization Model for the Wasserstein Barycenter Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GETO-LP, a linear programming formulation of the fixed-support Wasserstein barycenter problem on d-dimensional grids that reduces the variable count from O(MN^2) to O(dMN^{1+1/d}).
Problem
Computing fixed-support Wasserstein barycenters of M distributions is expensive because standard LP formulations need O(MN^2) variables, which is intractable for large grid supports.
Approach
Exploits the grid structure of the support to build a sparser LP with O(dMN^{1+1/d}) variables for the barycenter problem, instead of the dense per-pair transport plans of standard LP models.
Key results
- GETO-LP reduces the number of LP variables from O(MN^2) to O(dMN^{1+1/d}) for M distributions on a d-dimensional grid with N total support points.
Limitations
- Applies only to distributions supported on d-dimensional grids (fixed-support setting).
Experimental setup
Baselines: standard LP models for fixed-support Wasserstein barycenter
Builds on: standard LP formulation of fixed-support Wasserstein barycenter
Closest papers by meaning
- Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization (ICML 2025 · similarity 0.93)
- Computing Optimal Transport Maps and Wasserstein Barycenters Using Conditional Normalizing Flows (ICML 2025 · similarity 0.91)
- Estimating Barycenters of Distributions with Neural Optimal Transport (ICML 2024 · similarity 0.90)
- A Unified Approach for Computing Wasserstein Barycenters of Discrete and Continuous Measures (NeurIPS 2026 · similarity 0.89)
- Energy-Guided Continuous Entropic Barycenter Estimation for General Costs (NeurIPS 2024 · similarity 0.88)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.