Vi studerar det klassiska bipartite matchningsproblemet i online-miljön, som först introducerades i det seminala arbetet av Karp, Vazirani och Vazirani. Specifikt anser vi problemet för den välstuderade klassen av vanliga grafer. Matchning i denna klass av grafer studerades ingående i offline-inställningen. I online-inställningen var en optimal deterministisk algoritm, samt effektiva algoritmer under stokastiska indataantaganden kända. I detta arbete presenterar vi en ny randomiserad algoritm med konkurrensförhållande tendera till en på denna familj av grafer, under kontradiktorisk ankomst ordning. Vårt huvudsakliga bidrag är en ny algoritm som uppnår konkurrensförhållandet 1-O(\qrt{\log d}/\qrt{d}) i förväntan på d-regelbundna grafer. Däremot visar vi att alla tidigare kända online-algoritmer, såsom den i allmänhet sämsta fall optimala rankningsalgoritmen för Karp et al., är begränsade till ett konkurrensförhållande strikt avgränsat från en, även när d växer. Dessutom visar vi konvergensen i vår algoritms konkurrenskraft förhållande till en är nästan tight, eftersom ingen algoritm uppnår konkurrensförhållande bättre än 1-O(1/\qrt{d}). Slutligen visar vi att vår algoritm ger en liknande konkurrensförhållande med hög sannolikhet, samt garanterar varje offline vertex en sannolikhet att matchas tenderar att en.
Nyligen, Cohen och Wajc REF ansåg Online Bipartite Matching (med godtycklig ordning ankomst) på regelbundna diagram och gav en (1