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

DOI10.1007/978-3-030-04693-4_10MaRDI QIDQ1757767zbMATH OpenOpenAlexFDO

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

Publication date 15 January 2019

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

zbMATH Keywords

competitive ratioi.i.d. arrivalsperfect matching

Mathematics Subject Classification ID

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

Recommendations

• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• Online total bipartite matching problem
• Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• scientific article; zbMATH DE number 7376006

Cited in

(3)

• Online total bipartite matching problem
• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• 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

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