Improved Bounds for Online Stochastic Matching

DOI10.1007/978-3-642-15775-2_15zbMath1287.68184OpenAlexW1542279226MaRDI QIDQ3586460

Bahman Bahmani, Michael Kapralov

Publication date: 6 September 2010

Published in: Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15775-2_15

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Internet topics (68M11) Online algorithms; streaming algorithms (68W27)

Related Items (21)

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 ⋮ Online Stochastic Matching: Online Actions Based on Offline Statistics ⋮ A Dynamic Near-Optimal Algorithm for Online Linear Programming ⋮ An Experimental Study of Algorithms for Online Bipartite Matching ⋮ Advice complexity of online non-crossing matching ⋮ Dynamic Relaxations for Online Bipartite Matching ⋮ Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching ⋮ Unnamed Item ⋮ On extensions of the deterministic online model for bipartite matching and max-sat ⋮ Deferred on-line bipartite matching ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ 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 ⋮ Stochastic Online Metric Matching ⋮ Online Stochastic Matching: New Algorithms with Better Bounds ⋮ Learn from history for online bipartite matching ⋮ Unnamed Item

This page was built for publication: Improved Bounds for Online Stochastic Matching