Consensus-based Distributed Discrete Optimal Transport for Decentralized Resource Matching
arXiv:1904.04318
Abstract
Optimal transport has been used extensively in resource matching to promote the efficiency of resources usages by matching sources to targets. However, it requires a significant amount of computations and storage spaces for large-scale problems. In this paper, we take a consensus-based approach to decentralize discrete optimal transport problems and develop fully distributed algorithms with alternating direction method of multipliers. We show that our algorithms guarantee certain levels of efficiency and privacy besides the distributed nature. We further derive primal and dual algorithms by exploring the primal and dual problems of discrete optimal transport with linear utility functions and prove the equivalence between them. We verify the convergence, online adaptability, and the equivalence between the primal algorithm and the dual algorithm with numerical experiments. Our algorithms reflect the bargaining between sources and targets on the amounts and prices of transferred resources and reveal an averaging principle which can be used to regulate resource markets and improve resource efficiency.
References in corpus (8)
- A Quantitative Measure Of Fairness And Discrimination For Resource Allocation In Shared Computer Systems
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- Distributed Robust Multi-Cell Coordinated Beamforming with Imperfect CSI: An ADMM Approach
- Consensus-ADMM for General Quadratically Constrained Quadratic Programming
- Optimal Transport with Proximal Splitting
- Matching Demand with Supply in the Smart Grid using Agent-Based Multiunit Auction
- A Game-Theoretic Approach to Design Secure and Resilient Distributed Support Vector Machines
- A rigorous analysis using optimal transport theory for a two-reflector design problem with a point source