Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching
From MaRDI portal
Publication:897954
DOI10.1016/j.tcs.2015.05.032zbMath1332.68297OpenAlexW561882003MaRDI QIDQ897954
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
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