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

DOI10.1007/s00224-019-09947-7zbMath1442.90091arXiv1805.02014OpenAlexW2971819395MaRDI QIDQ2187342

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)

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

zbMATH Keywords

competitive ratioperfect matchingi.i.d. arrivals

Mathematics Subject Classification ID

Stochastic scheduling theory in operations research (90B36)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(k\)-server problem
• On-line algorithms for weighted bipartite matching and stable marriages
• Optimization for dynamic ride-sharing: a review
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• Bayesian Mechanism Design
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• Online Stochastic Weighted Matching: Improved Approximation Algorithms
• Competitive algorithms for server problems
• An O(log2 k)-Competitive Algorithm for Metric Bipartite Matching
• Randomized online algorithms for minimum metric bipartite matching
• A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
• Online Weighted Matching
• Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals
• Online Stochastic Matching: Beating 1-1/e
• k-server via multiscale entropic regularization
• Patient Choice in Kidney Allocation: A Sequential Stochastic Assignment Model
• Online bipartite matching with random arrivals

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