Now showing items 1-1 of 1

  • On-line algorithms for weighted bipartite matching and stable marriages 

    Khuller, Samir; Mitchell, Stephen G; Vazirani, Vijay V (1994)
    We give an on-line deterministic algorithm for the weighted bipartite matching problem that achieves a competitive ratio of (2n−1) in any metric space (where n is the number of vertices). This algorithm is optimal - there ...