Online Stochastic Weighted Matching: Improved Approximation Algorithms
From MaRDI portal
Publication:3102585
DOI10.1007/978-3-642-25510-6_15zbMath1398.68675OpenAlexW205662698MaRDI QIDQ3102585
Morteza Zadimoghaddam, Bernhard Haeupler, Vahab S. Mirrokni
Publication date: 5 December 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-25510-6_15
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Marketing, advertising (90B60) Internet topics (68M11) Online algorithms; streaming algorithms (68W27)
Related Items (22)
Online total bipartite matching problem ⋮ Technical Note—Assortment Planning for Two-Sided Sequential Matching Markets ⋮ A Polyhedral Approach to Online Bipartite Matching ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ Bicriteria Online Matching: Maximizing Weight and Cardinality ⋮ Near optimal algorithms for online weighted bipartite matching in adversary model ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Advice complexity of online non-crossing matching ⋮ Online stochastic weighted matching algorithm for real‐time shared parking ⋮ 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 ⋮ 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 submodular maximization: beating 1/2 made simple ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Online Stochastic Matching: New Algorithms with Better Bounds ⋮ Learn from history for online bipartite matching ⋮ Unnamed Item
This page was built for publication: Online Stochastic Weighted Matching: Improved Approximation Algorithms
