Approximation algorithms for stochastic online matching with reusable resources

Meghan Shanks (), Ge Yu and Sheldon H. Jacobson
Additional contact information
Meghan Shanks: University of Illinois at Urbana-Champaign
Ge Yu: Amazon Inc.
Sheldon H. Jacobson: University of Illinois at Urbana-Champaign

Mathematical Methods of Operations Research, 2023, vol. 98, issue 1, No 3, 43-56

Abstract: 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.

Keywords: Approximation algorithms; Online algorithms; Stochastic matching; Reusable resources (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-023-00822-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:98:y:2023:i:1:d:10.1007_s00186-023-00822-3

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-023-00822-3

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().