Online total bipartite matching problem

Meghan Shanks, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review

Abstract

This paper analyzes a variant of Online Bipartite Matching in which incoming jobs must be matched to some worker, even if there are no available edges. A reward is only gained for matchings that are made across some edge. This paper gives matching upper and lower bounds for the most general version of this variation. It then provides an optimal policy for this problem when the underlying bipartite graph meets certain conditions and then identifies the most general conditions under which this policy is guaranteed to be optimal.

Original languageEnglish (US)
Pages (from-to)1411-1426
Number of pages16
JournalOptimization Letters
Volume16
Issue number5
DOIs
StatePublished - Jun 2022
Externally publishedYes

Keywords

  • Bipartite matching
  • Online algorithms
  • Randomized algorithms

ASJC Scopus subject areas

  • Control and Optimization
  • Business, Management and Accounting (miscellaneous)

Fingerprint

Dive into the research topics of 'Online total bipartite matching problem'. Together they form a unique fingerprint.

Cite this