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 language | English (US) |
---|---|
Pages (from-to) | 1411-1426 |
Number of pages | 16 |
Journal | Optimization Letters |
Volume | 16 |
Issue number | 5 |
DOIs | |
State | Published - Jun 2022 |
Externally published | Yes |
Keywords
- Bipartite matching
- Online algorithms
- Randomized algorithms
ASJC Scopus subject areas
- Business, Management and Accounting (miscellaneous)
- Control and Optimization