Online algorithms for maximum cardinality matching with edge arrivals

DOI10.4230/LIPICS.ESA.2017.22MaRDI QIDQ5111708zbMATH OpenOpenAlexFDO

Authors Niv Buchbinder, Danny Segev, Yevgeny Tkach

Publication date 27 May 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/esa/esa2017.html#BuchbinderST17

zbMATH Keywords

competitive analysismaximum matchingonline algorithmsprimal-dual method

Mathematics Subject Classification ID

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

Recommendations

• Online algorithms for maximum cardinality matching with edge arrivals
• Maximum matching in the online batch-arrival model
• Online maximum matching with recourse
• Maximum matching on trees in the online preemptive and the incremental graph models
• Maximum matching on trees in the online preemptive and the incremental dynamic graph models

Cites work

• AdWords and generalized online matching
• An optimal deterministic algorithm for online \(b\)-matching
• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• Improved bounds for online preemptive matching
• Maximum matching on trees in the online preemptive and the incremental dynamic graph models
• On randomized algorithms for matching in the online preemptive model
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• Online lower bounds via duality
• Online matching and ad allocation
• Online matching with concave returns
• Online matroid intersection: beating half for random arrival
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
• Online Stochastic Matching: Beating 1-1/e
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Randomized primal-dual analysis of RANKING for online bipartite matching
• Two-sided online bipartite matching and vertex cover: beating the greedy algorithm

Cited in

(9)

• Online algorithms for maximum cardinality matching with edge arrivals
• Maximum matching on trees in the online preemptive and the incremental graph models
• Maximum matching in the online batch-arrival model
• Maximum matching on trees in the online preemptive and the incremental dynamic graph models
• Online maximum matching with recourse
• Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
• Maximum Matching in the Online Batch-arrival Model
• The online piercing set problem with recourse
• Online maximum matching with recourse

This page was built for publication: Online algorithms for maximum cardinality matching with edge arrivals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111708)