Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model

DOI10.1007/978-3-030-94676-0_12OpenAlexW4205598973MaRDI QIDQ2152115FDOQ2152115

Authors Billy Jin, David P. Williamson 

Publication date 6 July 2022

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

zbMATH Keywords

online algorithmsbipartite matching

Mathematics Subject Classification ID

Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26) Internet topics (68M11)

Recommendations

• scientific article; zbMATH DE number 7376006
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• Randomized primal-dual analysis of RANKING for online bipartite matching
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Tighter bounds for online bipartite matching

Cites work

• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Improved Bounds for Online Stochastic Matching
• New algorithms, better bounds, and a novel model for online stochastic matching
• Online Stochastic Matching: Beating 1-1/e
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• Online matching and ad allocation
• Online stochastic matching: new algorithms with better bounds
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
• Randomized primal-dual analysis of RANKING for online bipartite matching

Cited in

(3)

• Improved competitive ratio for edge-weighted online stochastic matching
• Online matching with stochastic rewards: advanced analyses using configuration linear programs
• Edge-weighted online bipartite matching

This page was built for publication: Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model

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