An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals

DOI10.1007/S00224-019-09947-7zbMATH Open1442.90091arXiv1805.02014OpenAlexW2971819395MaRDI QIDQ2187342FDOQ2187342

Dorit S. Hochbaum, Quico Spaen, Mark Velednitsky, Minjun Chang

Publication date: 2 June 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: This work presents an optimally-competitive algorithm for the problem of maximum weighted online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a known set of workers, a distribution over job types, and non-negative utility weights for each pair of worker and job types. At each time step, a job is drawn i.i.d. from the distribution over job types. Upon arrival, the job must be irrevocably assigned to a worker and cannot be dropped. The goal is to maximize the expected sum of utilities after all jobs are assigned. We introduce DISPATCH, a 0.5-competitive, randomized algorithm. We also prove that 0.5-competitive is the best possible. DISPATCH first selects a "preferred worker" and assigns the job to this worker if it is available. The preferred worker is determined based on an optimal solution to a fractional transportation problem. If the preferred worker is not available, DISPATCH randomly selects a worker from the available workers. We show that DISPATCH maintains a uniform distribution over the workers even when the distribution over the job types is non-uniform.

Full work available at URL: https://arxiv.org/abs/1805.02014

Recommendations

zbMATH Keywords

competitive ratio perfect matching i.i.d. arrivals

Mathematics Subject Classification ID

Stochastic scheduling theory in operations research (90B36)

Cites Work

Cited In (3)

This page was built for publication: An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2187342)