# Decentralized and Equitable Optimal Transport

arXiv: https://arxiv.org/abs/2403.04259 · HTML: https://mlsanity.com/paper/2403.04259/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 26 references that are in the map.
- First posted on arXiv 7 Mar 2024.

## Builds on (most cited first, 18 of 18)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019)
- [Quadratically regularized optimal transport](https://mlsanity.com/paper/1903.01112/) (2019)
- [Accelerated Bregman Primal-Dual methods applied to Optimal Transport and Wasserstein Barycenter problems](https://mlsanity.com/paper/2203.00802/) (2022)
- [Tracking-ADMM for Distributed Constraint-Coupled Optimization](https://mlsanity.com/paper/1907.10860/) (2019)
- [Fair and Distributed Dynamic Optimal Transport for Resource Allocation over Networks](https://mlsanity.com/paper/2103.16618/) (2021)
- [On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport](https://mlsanity.com/paper/2109.15030/) (2021)
- [A Proximal Diffusion Strategy for Multi-Agent Optimization with Sparse Affine Constraints](https://mlsanity.com/paper/1810.02124/) (2018)
- [Consensus-based Distributed Discrete Optimal Transport for Decentralized Resource Matching](https://mlsanity.com/paper/1904.04318/) (2019)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization](https://mlsanity.com/paper/1409.3307/) (2014)
- [Implicit Tracking-Based Distributed Constraint-Coupled Optimization](https://mlsanity.com/paper/2201.07627/) (2022)
- [Decentralized Entropic Optimal Transport for Distributed Distribution Comparison](https://mlsanity.com/paper/2301.12065/) (2023)
- [Algorithms for Euclidean-regularised Optimal Transport](https://mlsanity.com/paper/2307.00321/) (2023)

## Abstract (arXiv)

This paper considers the decentralized (discrete) optimal transport (D-OT) problem. In this setting, a network of agents seeks to design a transportation plan jointly, where the cost function is the sum of privately held costs for each agent. We reformulate the D-OT problem as a constraint-coupled optimization problem and propose a single-loop decentralized algorithm with an iteration complexity of O(1/ε) that matches existing centralized first-order approaches. Moreover, we propose the decentralized equitable optimal transport (DE-OT) problem. In DE-OT, in addition to cooperatively designing a transportation plan that minimizes transportation costs, agents seek to ensure equity in their individual costs. The iteration complexity of the proposed method to solve DE-OT is also O(1/ε). This rate improves existing centralized algorithms, where the best iteration complexity obtained is O(1/ε2).