Online weighted matching
Bala Kalyanasundaram, Kirk R. Pruhs · DIMACS series in discrete mathematics and theoretical computer science · 1992
Abstract We introduce and study online versions of weighted matching problems in metric spaces. We present a simple 2 k − 1 competitive algorithm for online minimum weighted bipartite matching where 2 k is the number of nodes. We show that this competitiveness is optimal. For online maximum matching, we prove that the greedy algorithm achieves an optimal competitive factor of 3. In contrast, we prove that the greedy algorithm performs exponentially poorly for online minimum matching.