Fractional Matching Via Balls-and-Bins

DOI10.1007/11830924_44zbMATH Open1155.05334OpenAlexW1508467588MaRDI QIDQ3595378FDOQ3595378

Authors: Rina Panigrahy, Ying Xu, Rajeev Motwani 

Publication date: 28 August 2007

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11830924_44

Recommendations

• Balls into bins made faster
• Tighter bounds for online bipartite matching
• Distributed near-optimal matching
• STACS 2004
• Perfect matchings via uniform sampling in regular bipartite graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (2)

• Efficient primal-dual graph algorithms for MapReduce
• Title not available (Why is that?)

This page was built for publication: Fractional Matching Via Balls-and-Bins

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