Abstract
We consider a class of stochastic online matching problems, where a set of sequentially arriving jobs are to be matched to a group of workers. The objective is to maximize the total expected reward, defined as the sum of the rewards of each matched worker-job pair. Each worker can be matched to multiple jobs subject to the constraint that previously matched jobs are completed. We provide constant approximation algorithms for different variations of this problem with equal-length jobs.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 43-56 |
| Number of pages | 14 |
| Journal | Mathematical Methods of Operations Research |
| Volume | 98 |
| Issue number | 1 |
| DOIs | |
| State | Published - Aug 2023 |
| Externally published | Yes |
Keywords
- Approximation algorithms
- Online algorithms
- Reusable resources
- Stochastic matching
ASJC Scopus subject areas
- Software
- General Mathematics
- Management Science and Operations Research