Editing Matching (graph theory) (section)

=== Online bipartite matching ===
The problem of developing an [[online algorithm]] for matching was first considered by [[Richard M. Karp]], [[Umesh Vazirani]], and [[Vijay Vazirani]] in 1990.<ref>{{cite conference|last1=Karp|first1=Richard M.|author1-link=Richard M. Karp|last2=Vazirani|first2=Umesh V.|author2-link=Umesh Vazirani|last3=Vazirani|first3=Vijay V.|author3-link=Vijay Vazirani|contribution=An optimal algorithm for on-line bipartite matching|contribution-url=https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf|doi=10.1145/100216.100262|pages=352–358|title=Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990)|year=1990|isbn=0-89791-361-2 }}</ref> 

In the online setting, nodes on one side of the bipartite graph arrive one at a time and must either be immediately matched to the other side of the graph or discarded. This is a natural generalization of the [[secretary problem]] and has applications to online ad auctions. The best online algorithm, for the unweighted maximization case with a random arrival model, attains a [[Competitive analysis (online algorithm)|competitive ratio]] of {{math|0.696}}.<ref>{{cite conference|last1=Mahdian|first1=Mohammad|last2=Yan|first2=Qiqi|doi=10.1145/1993636.1993716|title=Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing|pages=597–606|contribution=Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs|year=2011|doi-access=free}}</ref>