Online Matching in Regular Bipartite Graphs with Randomized Adversary

DOI10.1007/978-3-319-98355-4_17MaRDI QIDQ6163632zbMATH OpenOpenAlexFDO

Authors J. Fàbrega, Xavier Muñoz

Publication date 30 June 2023

Published in Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-98355-4_17

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)

Recommendations

• scientific article; zbMATH DE number 6850371
• Online matching in regular bipartite graphs
• Tighter bounds for online bipartite matching
• Near optimal algorithms for online weighted bipartite matching in adversary model
• Online bipartite matching with unknown distributions

Cites work

• AdWords and generalized online matching
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 2230243 (Why is no real title available?)
• Online algorithms. The state of the art
• Online graph coloring with advice and randomized adversary (extended abstract)
• Online matching in regular bipartite graphs
• Online Weighted Matching
• Randomized online algorithms for minimum metric bipartite matching
• The complexity of paging against a probabilistic adversary
• The CRC handbook of combinatorial designs

Cited in

(4)

• scientific article; zbMATH DE number 6850371 (Why is no real title available?)
• scientific article; zbMATH DE number 7376006 (Why is no real title available?)
• Adversarial resilience of matchings in bipartite random graphs
• Online matching in regular bipartite graphs

This page was built for publication: Online Matching in Regular Bipartite Graphs with Randomized Adversary

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