Randomized algorithm for MPMD on two sources

DOI10.1007/978-3-031-48974-7_20MaRDI QIDQ6609154

Kun He, Yuyi Wang, Weihao Zhu, Roger Wattenhofer, Sizhe Li, Enze Sun

Publication date: 20 September 2024

zbMATH Keywords

competitive analysislower boundrandomized algorithmsonline matching with delay

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the advice complexity of online bipartite matching and online stable marriage
• A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching
• Competitive randomized algorithms for nonuniform problems
• On-line algorithms for weighted bipartite matching and stable marriages
• Bayesian Mechanism Design
• AdWords and generalized online matching
• Randomized online algorithms for minimum metric bipartite matching
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Online Weighted Matching
• Min-Cost Bipartite Perfect Matching with Delays
• Impatient Online Matching
• Minimum Cost Perfect Matching with Delays for Two Sources
• Paths, Trees, and Flowers
• Online matching: haste makes waste!
• Maximum matching and a polyhedron with 0,1-vertices
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
• Deterministic min-cost matching with delays

This page was built for publication: Randomized algorithm for MPMD on two sources