Online Stochastic Matching: New Algorithms with Better Bounds

DOI10.1287/moor.2013.0621zbMath1323.68576OpenAlexW2029945631MaRDI QIDQ5244859

Patrick Jaillet, Xin Lu

Publication date: 31 March 2015

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2013.0621

zbMATH Keywords

stochastic optimizationonline bipartite matchingoffline linear programming bounds

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (24)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Online total bipartite matching problem ⋮ 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 ⋮ Near optimal algorithms for online weighted bipartite matching in adversary model ⋮ An Experimental Study of Algorithms for Online Bipartite Matching ⋮ 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 ⋮ Unnamed Item ⋮ Optimal dynamic multi-keyword bidding policy of an advertiser in search-based advertising ⋮ On Matching and Thickness in Heterogeneous Dynamic Markets ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Greedy Bipartite Matching in Random Type Poisson Arrival Model ⋮ Online stochastic matching: new algorithms and bounds ⋮ 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 Vertex-Weighted Bipartite Matching ⋮ Learn from history for online bipartite matching ⋮ Unnamed Item

Cites Work

• An optimal deterministic algorithm for online \(b\)-matching
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• A Dynamic Near-Optimal Algorithm for Online Linear Programming
• Online Stochastic Weighted Matching: Improved Approximation Algorithms
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
• AdWords and generalized online matching
• Improved Bounds for Online Stochastic Matching
• Online Stochastic Matching: Beating 1-1/e
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Online Stochastic Matching: New Algorithms with Better Bounds