Optimal Algorithms for Online b-Matching with Variable Vertex Capacities

DOI10.4230/LIPICS.APPROX/RANDOM.2021.2MaRDI QIDQ6070372zbMATH OpenOpenAlexFDO

Authors Susanne Albers

Publication date 20 November 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2021/14695/pdf/LIPIcs-APPROX2.pdf/

zbMATH Keywords

\(b\)-matchingconfiguration LPonline algorithmsprimal-dual analysisunweighted matchingvariable vertex capacitiesvertex-weighted matching

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• An optimal deterministic algorithm for online b-matching
• An optimal deterministic algorithm for online \(b\)-matching
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching

Cited in

(4)

• An optimal deterministic algorithm for online b-matching
• Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue
• Towards a practical, budget-oblivious algorithm for the adwords problem under small bids
• Towards a practical, budget-oblivious algorithm for the adwords problem under small bids

This page was built for publication: Optimal Algorithms for Online b-Matching with Variable Vertex Capacities

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