Online algorithms for maximum cardinality matching with edge arrivals

DOI10.1007/s00453-018-0505-7zbMath1422.68321OpenAlexW2889345925WikidataQ129336161 ScholiaQ129336161MaRDI QIDQ1741843

Yevgeny Tkach, Niv Buchbinder, Danny Segev

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7820/

zbMATH Keywords

primal-dual methodcompetitive analysisonline algorithmsmaximum matching

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 (2)

Prophet Matching with General Arrivals ⋮ Computing maximum matchings in temporal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal deterministic algorithm for online \(b\)-matching
• Improved bounds for randomized preemptive online matching
• Online matroid intersection: beating half for random arrival
• Maximum matching on trees in the online preemptive and the incremental dynamic graph models
• Bayesian Mechanism Design
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
• On Randomized Algorithms for Matching in the Online Preemptive Model
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
• AdWords and generalized online matching
• Online Lower Bounds via Duality
• Online Stochastic Matching: Beating 1-1/e
• 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: Online algorithms for maximum cardinality matching with edge arrivals