On the power of advice and randomization for online bipartite matching

DOI10.4230/LIPICS.ESA.2016.37MaRDI QIDQ4606307zbMATH OpenFDO

Authors Christian Konrad, Marc P. Renault, Christoph Dürr

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1602.07154

zbMATH Keywords

randomizationonline algorithmsbipartite matching

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Online matching in regular bipartite graphs
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• On the advice complexity of online bipartite matching and online stable marriage
• Randomization can be as helpful as a glimpse of the future in online computation
• On the power of randomness versus advice in online computation

Cited in

(12)

• Temporal matching on geometric graph data
• The power of multiple choices in online stochastic matching
• Temporal matching
• On the advice complexity of online bipartite matching and online stable marriage
• Online matching in regular bipartite graphs
• Weighted Online Problems with Advice
• Advice complexity of online non-crossing matching
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• An Experimental Study of Algorithms for Online Bipartite Matching
• On extensions of the deterministic online model for bipartite matching and max-sat
• Online bin covering with advice
• A simple PTAS for the dual bin packing problem and advice complexity of its online version

This page was built for publication: On the power of advice and randomization for online bipartite matching

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