Online Stochastic Matching: Online Actions Based on Offline Statistics
From MaRDI portal
Publication:2925346
DOI10.1287/moor.1120.0551zbMath1297.68269arXiv1007.1673OpenAlexW2571343094MaRDI QIDQ2925346
Shayan Oveis Gharan, V. H. Manshadi, Amin Saberi
Publication date: 21 October 2014
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1007.1673
Analysis of algorithms (68W40) Applications of graph theory (05C90) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (40)
Approximation algorithms for stochastic combinatorial optimization problems ⋮ Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm ⋮ Online total bipartite matching problem ⋮ Technical Note—Assortment Planning for Two-Sided Sequential Matching Markets ⋮ Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model ⋮ A Polyhedral Approach to Online Bipartite Matching ⋮ Online spatio-temporal matching in stochastic and dynamic domains ⋮ A stochastic algorithm for online bipartite resource allocation problems ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ Near optimal algorithms for online weighted bipartite matching in adversary model ⋮ Primal-dual analysis for online interval scheduling problems ⋮ An Experimental Study of Algorithms for Online Bipartite Matching ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Approximation algorithms for stochastic online matching with reusable resources ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ Advice complexity of online non-crossing matching ⋮ Online stochastic weighted matching algorithm for real‐time shared parking ⋮ Dynamic Stochastic Matching Under Limited Time ⋮ Dynamic Relaxations for Online Bipartite Matching ⋮ Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching ⋮ Max-min greedy matching problem: hardness for the adversary and fractional variant ⋮ Unnamed Item ⋮ Approximations to Stochastic Dynamic Programs via Information Relaxation Duality ⋮ On Matching and Thickness in Heterogeneous Dynamic Markets ⋮ Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Online algorithms for maximum cardinality matching with edge arrivals ⋮ Greedy Bipartite Matching in Random Type Poisson Arrival Model ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ Online stochastic matching: new algorithms and bounds ⋮ Unnamed Item ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts ⋮ A polyhedral approach to online bipartite matching ⋮ Online submodular maximization: beating 1/2 made simple ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Online Algorithms for Maximum Cardinality Matching with Edge Arrivals ⋮ Online Stochastic Matching: New Algorithms with Better Bounds ⋮ Learn from history for online bipartite matching ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Sharp load thresholds for cuckoo hashing
- Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables
- AdWords and generalized online matching
- Improved Bounds for Online Stochastic Matching
- Tight Thresholds for Cuckoo Hashing via XORSAT
- Cuckoo hashing
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals
This page was built for publication: Online Stochastic Matching: Online Actions Based on Offline Statistics
