Online total bipartite matching problem

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.

Automated summary

This paper analyzes a variant of Online Bipartite Matching where incoming jobs need to be matched to workers even without available edges. A reward is only obtained for matchings made across an edge. The paper provides upper and lower bounds for the most general version of this variant and presents an optimal policy for this problem under certain conditions in the underlying bipartite graph.