scientific article; zbMATH DE number 6850371

MaRDI QIDQ4607945zbMATH OpenFDO

Authors Ilan Reuven Cohen, David Wajc

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175332

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Recommendations

• Online matching in regular bipartite graphs
• Online Matching in Regular Bipartite Graphs with Randomized Adversary
• Markovian online matching algorithms on large bipartite random graphs
• On randomized algorithms for matching in the online preemptive model
• Online stochastic matching: new algorithms and bounds
• scientific article; zbMATH DE number 1033855
• Online stochastic matching: new algorithms with better bounds
• Random matchings in regular graphs
• Online maximum matching with recourse

Cited in

(24)

• Improved bounds for randomized preemptive online matching
• Online minimum matching with uniform metric and random arrivals
• Markovian online matching algorithms on large bipartite random graphs
• Improved bounds for online preemptive matching
• On randomized algorithms for matching in the online preemptive model
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• scientific article; zbMATH DE number 7376006 (Why is no real title available?)
• Max-min greedy matching
• Online matching in regular bipartite graphs
• Stochastic online metric matching
• scientific article; zbMATH DE number 7650074 (Why is no real title available?)
• Online allocation and display ads optimization with surplus supply
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• Online Matching in Regular Bipartite Graphs with Randomized Adversary
• Online Edge Coloring via Tree Recurrences and Correlation Decay
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• Improved competitive ratio for edge-weighted online stochastic matching
• Online algorithm for fractional matchings with edge arrivals in graphs of maximum degree three
• Online matching for the multiclass stochastic block model
• Tight bounds for online matching in bounded-degree graphs with vertex capacities
• Online matching with high probability
• Online stochastic matching with edge arrivals
• The greedy algorithm is not optimal for on-line edge coloring
• Optimal online bipartite matching in degree-2 graphs

This page was built for publication:

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