Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching

DOI10.1137/1.9781611973105.7zbMath1421.68244OpenAlexW4250340495MaRDI QIDQ5741715

No author found.

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.7

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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 (28)

Minimum cost perfect matching with delays for two sources ⋮ A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines ⋮ Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm ⋮ Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model ⋮ 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 ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ Advice complexity of online non-crossing matching ⋮ Online allocation and display ads optimization with surplus supply ⋮ Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching ⋮ Unnamed Item ⋮ Online Edge Coloring via Tree Recurrences and Correlation Decay ⋮ Clinching auctions with online supply ⋮ Tighter Bounds for Online Bipartite Matching ⋮ 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 ⋮ Stable secretaries ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Shortest Augmenting Paths for Online Matchings on Trees ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Impatient Online Matching ⋮ Size versus truthfulness in the house allocation problem ⋮ On Policies for Single-Leg Revenue Management with Limited Demand Information ⋮ Online Algorithms for Maximum Cardinality Matching with Edge Arrivals ⋮ Online Submodular Maximization Problem with Vector Packing Constraint. ⋮ Learn from history for online bipartite matching

This page was built for publication: Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching