Skip to main content
Top

2019 | OriginalPaper | Chapter

Tighter Bounds for Online Bipartite Matching

Author : Uriel Feige

Published in: Building Bridges II

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We study the online bipartite matching problem, introduced by Karp, Vazirani and Vazirani [1990]. For bipartite graphs with matchings of size n, it is known that the Ranking randomized algorithm matches at least \((1 - \frac{1}{e})n\) edges in expectation. It is also known that no online algorithm matches more than \((1 - \frac{1}{e})n + O(1)\) edges in expectation, when the input is chosen from a certain distribution that we refer to as \(D_n\). This upper bound also applies to fractional matchings. We review the known proofs for this last statement. In passing we observe that the O(1) additive term (in the upper bound for fractional matching) is \(\frac{1}{2} - \frac{1}{2e} + O(\frac{1}{n})\), and that this term is tight: the online algorithm known as Balance indeed produces a fractional matching of this size. We provide a new proof that exactly characterizes the expected cardinality of the (integral) matching produced by Ranking when the input graph comes from the support of \(D_n\). This expectation turns out to be \((1 - \frac{1}{e})n + 1 - \frac{2}{e} + O(\frac{1}{n!})\), and serves as an upper bound on the performance ratio of any online (integral) matching algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Literature
1.
go back to reference Benjamin E. Birnbaum, Claire Mathieu: On-line bipartite matching made simple. SIGACT News 39(1), 80–87 (2008)CrossRef Benjamin E. Birnbaum, Claire Mathieu: On-line bipartite matching made simple. SIGACT News 39(1), 80–87 (2008)CrossRef
2.
go back to reference Nikhil R. Devanur, Kamal Jain, Robert D Kleinberg: Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching. SODA 2013: 101–107 Nikhil R. Devanur, Kamal Jain, Robert D Kleinberg: Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching. SODA 2013: 101–107
4.
go back to reference Gagan Goel, Aranyak Mehta: Online budgeted matching in random input models with applications to Adwords. SODA 2008: 982–991. Gagan Goel, Aranyak Mehta: Online budgeted matching in random input models with applications to Adwords. SODA 2008: 982–991.
5.
go back to reference Bala Kalyanasundaram, Kirk Pruhs: An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci. 233(1-2): 319–325 (2000).MathSciNetCrossRef Bala Kalyanasundaram, Kirk Pruhs: An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci. 233(1-2): 319–325 (2000).MathSciNetCrossRef
7.
go back to reference Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani: An Optimal Algorithm for On-line Bipartite Matching. STOC 1990: 352–358. Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani: An Optimal Algorithm for On-line Bipartite Matching. STOC 1990: 352–358.
9.
go back to reference L. Lovasz, M. D. Plummer. Matching Theory. Elsevier 1986. L. Lovasz, M. D. Plummer. Matching Theory. Elsevier 1986.
11.
go back to reference Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013.MathSciNetCrossRef Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013.MathSciNetCrossRef
12.
go back to reference Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani: AdWords and generalized online matching. J. ACM 54(5): 22 (2007).MathSciNetCrossRef Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani: AdWords and generalized online matching. J. ACM 54(5): 22 (2007).MathSciNetCrossRef
Metadata
Title
Tighter Bounds for Online Bipartite Matching
Author
Uriel Feige
Copyright Year
2019
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-59204-5_7

Premium Partner