TY - JOUR

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

AU - Khuller, Samir

AU - Mitchell, Stephen G.

AU - Vazirani, Vijay V.

PY - 1994/5/23

Y1 - 1994/5/23

N2 - 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 is no on-line deterministic algorithm that achieves a competitive ratio better than (2n-1) in all metric spaces. We also study the stable marriage problem, where we are interested in the number of unstable pairs produced. We show that the simple "first come, first served" deterministic algorithm yields on the average O(n log n) unstable pairs, but in the worst case no deterministic or randomized on-line algorithm can do better than ω(n2) unstable pairs. This appears to be the first on-line problem for which provably one cannot do better with randomization; for most on-line problems studied in the past, randomization has helped in improving the performance.

AB - 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 is no on-line deterministic algorithm that achieves a competitive ratio better than (2n-1) in all metric spaces. We also study the stable marriage problem, where we are interested in the number of unstable pairs produced. We show that the simple "first come, first served" deterministic algorithm yields on the average O(n log n) unstable pairs, but in the worst case no deterministic or randomized on-line algorithm can do better than ω(n2) unstable pairs. This appears to be the first on-line problem for which provably one cannot do better with randomization; for most on-line problems studied in the past, randomization has helped in improving the performance.

UR - http://www.scopus.com/inward/record.url?scp=0028425278&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028425278&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(94)90042-6

DO - 10.1016/0304-3975(94)90042-6

M3 - Article

AN - SCOPUS:0028425278

SN - 0304-3975

VL - 127

SP - 255

EP - 267

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

ER -