Consensus-based distributed discrete optimal transport for decentralized resource matching

Rui Zhang, Quanyan Zhu

Research output: Contribution to journalArticle

Abstract

Optimal transport has been extensively used in resource matching to promote the efficiency of resource 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.

Original languageEnglish (US)
Article number8686135
Pages (from-to)511-524
Number of pages14
JournalIEEE Transactions on Signal and Information Processing over Networks
Volume5
Issue number3
DOIs
StatePublished - Sep 2019

Keywords

  • Optimal transport
  • alternating direction method of multipliers
  • consensus-based decentralization
  • distributed resource matching
  • resource allocation
  • resource markets

ASJC Scopus subject areas

  • Signal Processing
  • Information Systems
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Consensus-based distributed discrete optimal transport for decentralized resource matching'. Together they form a unique fingerprint.

  • Cite this