### 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 Ω(n^{2}) 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 language | English (US) |
---|---|

Title of host publication | Automata, Languages and Programming - 18th International Colloquium, Proceedings |

Editors | Javier Leach Albert, Mario Rodriguez Artalejo, Burkhard Monien |

Publisher | Springer Verlag |

Pages | 728-738 |

Number of pages | 11 |

ISBN (Print) | 9783540542339 |

DOIs | |

State | Published - Jan 1 1991 |

Event | 18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991 - Madrid, Spain Duration: Jul 8 1991 → Jul 12 1991 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 510 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991 |
---|---|

Country | Spain |

City | Madrid |

Period | 7/8/91 → 7/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

*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