Adaptive dynamic bipartite graph matching: A reinforcement learning approach

Yansheng Wang, Yongxin Tong, Cheng Long, Pan Xu, Ke Xu, Weifeng Lv

Research output: Chapter in Book/Report/Conference proceedingConference contribution

85 Scopus citations

Abstract

Online bipartite graph matching is attracting growing research attention due to the development of dynamic task assignment in sharing economy applications, where tasks need be assigned dynamically to workers. Past studies lack practicability in terms of both problem formulation and solution framework. On the one hand, some problem settings in prior online bipartite graph matching research are impractical for real-world applications. On the other hand, existing solutions to online bipartite graph matching are inefficient due to the unnecessary real-time decision making. In this paper, we propose the dynamic bipartite graph matching (DBGM) problem to be better aligned with real-world applications and devise a novel adaptive batch-based solution framework with a constant competitive ratio. As an effective and efficient implementation of the solution framework, we design a reinforcement learning based algorithm, called Restricted Q-learning (RQL), which makes near-optimal decisions on batch splitting. Extensive experimental results on both real and synthetic datasets show that our methods outperform the state-of-the-arts in terms of both effectiveness and efficiency.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
PublisherIEEE Computer Society
Pages1478-1489
Number of pages12
ISBN (Electronic)9781538674741
DOIs
StatePublished - Apr 2019
Externally publishedYes
Event35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, China
Duration: Apr 8 2019Apr 11 2019

Publication series

NameProceedings - International Conference on Data Engineering
Volume2019-April
ISSN (Print)1084-4627

Conference

Conference35th IEEE International Conference on Data Engineering, ICDE 2019
Country/TerritoryChina
CityMacau
Period4/8/194/11/19

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems

Keywords

  • Bipartite graph matching
  • Online algorithm
  • Reinforcement learning

Fingerprint

Dive into the research topics of 'Adaptive dynamic bipartite graph matching: A reinforcement learning approach'. Together they form a unique fingerprint.

Cite this