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 (4)

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

This page was built for publication: Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching