Online matching: haste makes waste!

DOI10.1145/2897518.2897557zbMath1376.68174arXiv1603.03024OpenAlexW2295274877MaRDI QIDQ5361841

Yuval Emek, Shay Kutten, Roger Wattenhofer

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

online matchingdelayed servicealternate Poisson processmetric MIN-cost perfect matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Online algorithms; streaming algorithms (68W27)

Related Items (12)

Minimum cost perfect matching with delays for two sources ⋮ Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities ⋮ Caching with Time Windows and Delays ⋮ Technical Note—Online Hypergraph Matching with Delays ⋮ Unnamed Item ⋮ On bin packing with clustering and bin packing with delays ⋮ The k-Server Problem with Delays on the Uniform Metric Space ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Stable secretaries ⋮ Deterministic min-cost matching with delays ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Impatient Online Matching

This page was built for publication: Online matching: haste makes waste!