On-line algorithms for weighted bipartite matching and stable marriages

Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

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. 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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 18th International Colloquium, Proceedings
EditorsJavier Leach Albert, Mario Rodriguez Artalejo, Burkhard Monien
PublisherSpringer Verlag
Pages728-738
Number of pages11
ISBN (Print)9783540542339
DOIs
StatePublished - Jan 1 1991
Event18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991 - Madrid, Spain
Duration: Jul 8 1991Jul 12 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume510 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991
CountrySpain
CityMadrid
Period7/8/917/12/91

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On-line algorithms for weighted bipartite matching and stable marriages'. Together they form a unique fingerprint.

  • Cite this

    Khuller, S., Mitchell, S. G., & Vazirani, V. V. (1991). On-line algorithms for weighted bipartite matching and stable marriages. In J. L. Albert, M. R. Artalejo, & B. Monien (Eds.), Automata, Languages and Programming - 18th International Colloquium, Proceedings (pp. 728-738). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 510 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-54233-7_178