Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching
DOI10.1016/J.TCS.2015.05.032zbMATH Open1332.68297OpenAlexW561882003MaRDI QIDQ897954FDOQ897954
Authors: H. F. Ting, Xiangzhong Xiang 
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
Recommendations
- Near optimal algorithms for online maximum weighted \(b\)-matching
- Online vertex-weighted bipartite matching and single-bid budgeted allocations
- Online Weighted Matching
- Near optimal algorithms for online weighted bipartite matching in adversary model
- Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- AdWords and generalized online matching
- Online stochastic matching: online actions based on offline statistics
- Title not available (Why is that?)
- Improved Bounds for Online Stochastic Matching
- Online Stochastic Matching: Beating 1-1/e
- Online bipartite matching with unknown distributions
- Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
- Algorithms for Secretary Problems on Graphs and Hypergraphs
- An optimal deterministic algorithm for online \(b\)-matching
- Online vertex-weighted bipartite matching and single-bid budgeted allocations
- Online Weighted Matching
- Randomized primal-dual analysis of RANKING for online bipartite matching
- Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints
- Online stochastic weighted matching: improved approximation algorithms
Cited In (18)
- Biobjective online bipartite matching
- Bicriteria online matching: maximizing weight and cardinality
- An optimal deterministic algorithm for online b-matching
- Online crowdsourced truck delivery using historical information
- Title not available (Why is that?)
- DISPATCH: an optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
- Maximum Matching in the Online Batch-arrival Model
- Near optimal algorithms for online maximum weighted \(b\)-matching
- Two-sided online bipartite matching and vertex cover: beating the greedy algorithm
- Optimal Algorithms for Online b-Matching with Variable Vertex Capacities
- Online generalized assignment problem with historical information
- Near optimal algorithms for online weighted bipartite matching in adversary model
- Maximum matching in the online batch-arrival model
- An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
- Edge-weighted online bipartite matching
- Online bipartite matching with decomposable weights
- Learn from history for online bipartite matching
- Online vertex-weighted bipartite matching and single-bid budgeted allocations
This page was built for publication: Near optimal algorithms for online maximum edge-weighted \(b\)-matching and two-sided vertex-weighted \(b\)-matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897954)
