Online Stochastic Matching: Beating 1-1/e

DOI10.1109/FOCS.2009.72zbMath1292.68173OpenAlexW2170675255MaRDI QIDQ5171168

No author found.

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.72

Mathematics Subject Classification ID

Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Internet topics (68M11) Online algorithms; streaming algorithms (68W27)

Related Items (51)

Strategyproof mechanisms for competitive influence in networks ⋮ 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 ⋮ Online algorithms with advice for the dual bin packing problem ⋮ Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model ⋮ A Polyhedral Approach to Online Bipartite Matching ⋮ A stochastic algorithm for online bipartite resource allocation problems ⋮ Multiplicative Pacing Equilibria in Auction Markets ⋮ A Dynamic Near-Optimal Algorithm for Online Linear Programming ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ Greedy Matching in Bipartite Random Graphs ⋮ Asymptotic analysis for multi-objective sequential stochastic assignment problems ⋮ Bicriteria Online Matching: Maximizing Weight and Cardinality ⋮ Online Matching in Regular Bipartite Graphs ⋮ 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 ⋮ 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 ⋮ Markovian online matching algorithms on large bipartite random graphs ⋮ Unnamed Item ⋮ On Matching and Thickness in Heterogeneous Dynamic Markets ⋮ Station assignment with reallocation ⋮ Frequency capping in online advertising ⋮ 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 ⋮ On the on-line maintenance scheduling problem ⋮ New online algorithms for story scheduling in web advertising ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ 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 submodular maximization: beating 1/2 made simple ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Stochastic Online Metric Matching ⋮ Tractable Equilibria in Sponsored Search with Endogenous Budgets ⋮ Online Algorithms for Maximum Cardinality Matching with Edge Arrivals ⋮ Online Stochastic Matching: New Algorithms with Better Bounds ⋮ Budget-Management Strategies in Repeated Auctions ⋮ Learn from history for online bipartite matching ⋮ Unnamed Item ⋮ Auctions with online supply

This page was built for publication: Online Stochastic Matching: Beating 1-1/e