Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm

DOI10.1007/978-3-662-47672-7_87zbMath1422.68327OpenAlexW2295981146MaRDI QIDQ3448861

No author found.

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_87

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Online algorithms; streaming algorithms (68W27)

Related Items (13)

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty ⋮ Online spatio-temporal matching in stochastic and dynamic domains ⋮ Prophet Matching with General Arrivals ⋮ Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming ⋮ Unnamed Item ⋮ The power of amortized recourse for online graph problems ⋮ Temporal matching on geometric graph data ⋮ Algorithms for Queryable Uncertainty ⋮ Online algorithms for maximum cardinality matching with edge arrivals ⋮ Temporal matching ⋮ Online Vertex-Weighted Bipartite Matching ⋮ Randomization Helps Computing a Minimum Spanning Tree under Uncertainty ⋮ Online Algorithms for Maximum Cardinality Matching with Edge Arrivals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Competitive snoopy caching
• Competitive randomized algorithms for nonuniform problems
• An optimal deterministic algorithm for online \(b\)-matching
• On-line vertex-covering
• Bayesian Mechanism Design
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• Online algorithms for market clearing
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
• AdWords and generalized online matching
• When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
• Online Stochastic Matching: Beating 1-1/e
• Dynamic TCP acknowledgement and other stories about e/(e-1)
• Online matching with concave returns
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching

This page was built for publication: Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm