Learn from history for online bipartite matching

Huili Zhang, Rui Du, Kelin Luo and Weitian Tong ()
Additional contact information
Huili Zhang: Xi’an Jiaotong University
Rui Du: Xi’an Jiaotong University
Kelin Luo: University of Bonn
Weitian Tong: Georgia Southern University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 5, No 21, 3640 pages

Abstract: Abstract Motivated by various applications in the online platforms for ride-hailing and crowd-sourcing delivery, we study the edge-weighted online bipartite matching (EWOBM) problem. We assume a part of online vertices are released in advance to mimic historical information that the algorithm is able to access. Different from traditional approaches that usually learn informative distributions from large enough history sets, our algorithms enable to extra useful information for the history set of any size. When the online vertices arrive in a random order, we present an online algorithm, named as h -TP-OM, achieving a competitive ratio that increases as more historical information is considered. However, once enough historical information has been fed to the algorithm, additional historical information becomes useless. Based on h -TP-OM, we then propose a time-efficient greedy heuristic, named as h -TP-G, which even has better performances in applications, particularly on large-scale instances. When the arrival order of online vertices is determined by an adversary, we present another greedy heuristic algorithm, named as Greedy-RT. Experiments on both synthetic and real-world datasets are conducted to evaluate the practical performances of the proposed algorithms. The experiment results demonstrate the usefulness of historical information for both h -TP-OM and h -TP-G, and also show the time efficiency of h -TP-G and Greedy-RT.

Keywords: Online bipartite matching; Competitive ratio; Adversary-order model; Random-order model; Historical information (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00916-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:5:d:10.1007_s10878-022-00916-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00916-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().