A randomized algorithm for online metric b-matching

DOI10.1016/j.orl.2023.09.002MaRDI QIDQ6556181

Clifford Stein, Bala Kalyanasundaram, Kirk R. Pruhs

Publication date: 17 June 2024

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

zbMATH Keywords

matchingonline algorithmsmetric matching

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

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

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