scientific article; zbMATH DE number 7376006

DOI10.4230/LIPIcs.ICALP.2018.79zbMath1499.68414arXiv1804.07458MaRDI QIDQ5002758

Yu-Hao Zhang, Xiaowei Wu, Zhihao Gavin Tang, Zhi-Yi Huang

Publication date: 28 July 2021

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

online bipartite matchingvertex-weighted graphrandomized primal-dual

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items

Online Vertex-Weighted Bipartite Matching ⋮ Stochastic Online Metric Matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• Online Stochastic Weighted Matching: Improved Approximation Algorithms
• Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
• Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue
• AdWords and generalized online matching
• Improved Bounds for Online Stochastic Matching
• Randomized greedy matching. II
• Beating ratio 0.5 for weighted oblivious matching problems
• Secretary Problems via Linear Programming
• Online Stochastic Matching: Beating 1-1/e
• Online Stochastic Matching: New Algorithms with Better Bounds
• Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints
• Online matching with concave returns
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching