Dispatch: an optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals

DOI10.1007/978-3-030-04693-4_10OpenAlexW3102048106MaRDI QIDQ1757767

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

Publication date: 15 January 2019

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

zbMATH Keywords

competitive ratioperfect matchingi.i.d. arrivals

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Stochastic Online Metric Matching

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