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

DOI10.1016/J.TCS.2015.05.032MaRDI QIDQ897954zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

online algorithmslower boundscompetitive analysisupper boundsmaximum weighted matching

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• AdWords and generalized online matching
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• An optimal deterministic algorithm for online \(b\)-matching
• Improved Bounds for Online Stochastic Matching
• Online Stochastic Matching: Beating 1-1/e
• Online Weighted Matching
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• Online stochastic weighted matching: improved approximation algorithms
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Randomized primal-dual analysis of RANKING for online bipartite matching
• Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints

Cited in

(18)

• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• Maximum matching in the online batch-arrival model
• Two-sided online bipartite matching and vertex cover: beating the greedy algorithm
• Biobjective online bipartite matching
• Bicriteria online matching: maximizing weight and cardinality
• Edge-weighted online bipartite matching
• scientific article; zbMATH DE number 7376006 (Why is no real title available?)
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Online generalized assignment problem with historical information
• Near optimal algorithms for online weighted bipartite matching in adversary model
• Near optimal algorithms for online maximum weighted \(b\)-matching
• DISPATCH: an optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• Maximum Matching in the Online Batch-arrival Model
• Online crowdsourced truck delivery using historical information
• An optimal deterministic algorithm for online b-matching
• Online bipartite matching with decomposable weights
• Optimal Algorithms for Online b-Matching with Variable Vertex Capacities
• Learn from history 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897954)