Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching

DOI10.1016/j.tcs.2015.05.032zbMath1332.68297OpenAlexW561882003MaRDI QIDQ897954

Xiangzhong Xiang, H. F. Ting

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.05.032

zbMATH Keywords

upper boundscompetitive analysisonline algorithmslower boundsmaximum weighted matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Signed and weighted graphs (05C22) Online algorithms; streaming algorithms (68W27)

Related Items

Online crowdsourced truck delivery using historical information, Near optimal algorithms for online weighted bipartite matching in adversary model, Learn from history for online bipartite matching, Online generalized assignment problem with historical information

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal deterministic algorithm for online \(b\)-matching
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• Online Stochastic Weighted Matching: Improved Approximation Algorithms
• AdWords and generalized online matching
• Improved Bounds for Online Stochastic Matching
• Online Weighted Matching
• Online Stochastic Matching: Beating 1-1/e
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching