ONLINE ALGORITHMS FOR WEIGHTED BIPARTITE MATCHING AND STABLE MARRIAGES

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 op timal - there is no on-line deterministic algorithm that achieves a co mpetitive ratio better than (2n - 1) in all metric spaces. We also stu dy the stable marriage problem, where we are interested in the number of unstable pairs produced. We show that the simple ''first come, firs t served'' deterministic algorithm yields on the average O(n log n) un stable pairs, but in the worst case no deterministic or randomized on- line algorithm can do better than OMEGA(n2) unstable pairs. This appea rs to be the first on-line problem for which provably one cannot do be tter with randomization; for most on-line problems studied in the past , randomization has helped in improving the performance.