A randomized algorithm for online metric b-matching

DOI10.1016/J.ORL.2023.09.002MaRDI QIDQ6556181zbMATH OpenFDO

Authors Bala Kalyanasundaram, Kirk Pruhs, Clifford Stein

Publication date 17 June 2024

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ORL.2023.09.002

zbMATH Keywords

matchingmetric matchingonline algorithms

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites work

• A randomized O(^2k)-competitive algorithm for metric bipartite matching
• A tight bound on approximating arbitrary metrics by tree metrics
• On-line algorithms for weighted bipartite matching and stable marriages
• Online Weighted Matching
• Randomized online algorithms for minimum metric bipartite matching

Cited in

(1)

• A nearly optimal deterministic algorithm for online transportation problem

This page was built for publication: A randomized algorithm for online metric b-matching

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