Online total bipartite matching problem

Meghan Shanks, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review


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
Issue number5
StatePublished - Jun 2022
Externally publishedYes


  • Bipartite matching
  • Online algorithms
  • Randomized algorithms

ASJC Scopus subject areas

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


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

Cite this