Online Vertex-Weighted Bipartite Matching
From MaRDI portal
Publication:4972684
DOI10.1145/3326169zbMath1455.68278OpenAlexW2952720641WikidataQ127671880 ScholiaQ127671880MaRDI QIDQ4972684
Yu-Hao Zhang, Xiaowei Wu, Zhihao Gavin Tang, Zhi-Yi Huang
Publication date: 25 November 2019
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3326169
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
Improved analysis of RANKING for online vertex-weighted bipartite matching in the random order model ⋮ Secretary and online matching problems with machine learned advice ⋮ Best fit bin packing with random order revisited ⋮ Best Fit Bin Packing with Random Order Revisited ⋮ Learn from history for online bipartite matching
Cites Work
- Unnamed Item
- 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
- Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity
- Beating ratio 0.5 for weighted oblivious matching problems
- Secretary Problems via Linear Programming
- Online Stochastic Matching: Beating 1-1/e
- How to match when all vertices arrive online
- 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