A randomized algorithm for the on-line weighted bipartite matching problem

DOI10.1007/S10951-007-0037-5zbMath1176.68239arXiv0705.4673OpenAlexW2125120324MaRDI QIDQ835627

András Pluhár, Béla Csaba

Publication date: 28 August 2009

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0705.4673

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (3)

Greedy metric minimum online matchings with random arrivals ⋮ Randomized algorithm for the \(k\)-server problem on decomposable spaces ⋮ Competitive strategies for an online generalized assignment problem with a service consecution constraint

Cites Work

• Unnamed Item
• Unnamed Item
• On-line algorithms for weighted bipartite matching and stable marriages
• Randomized online algorithms for minimum metric bipartite matching
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Online Weighted Matching
• Approximation and Online Algorithms
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: A randomized algorithm for the on-line weighted bipartite matching problem