Vi introducerar en helt online modell av maximal kardinalitet matchning där alla hörn anländer online. Vid ankomsten av en vertex, dess incident kanter till tidigare anlända hörn avslöjas. Varje vertex har en deadline som är efter alla dess grannars ankomster. Om en vertex förblir oöverträffad fram till dess deadline, algoritmen måste då oåterkalleligen antingen matcha den med en oöverträffad granne, eller lämna den oöverträffad. Modellen generaliserar den befintliga ensidiga online-modellen och motiveras av applikationer som ride-sharing-plattformar, fastighetsbyrå, etc. Vi visar att Ranking algoritm av Karp et al. (STOC 1990) är 0,5211-konkurrenskraftig i vår helt online-modell för allmänna grafer. Vår analys ger en ny laddningsmekaniker in i den randomiserade primal dual tekniken av Devanur et al. (SODA 2013) som gör det möjligt att dela vinsten med en annan vertex än de två effektmåtten för en matchad kant. Till vår kännedom är detta den första analysen av Ranking som slår 0,5 på allmänna grafer i ett online matchande problem, ett första steg mot att lösa det öppna problemet av Karp et al. (STOC 1990) om optimaliteten av Ranking på allmänna grafer. Om grafen är bipartit, visar vi att konkurrensförhållandet för Ranking är mellan 0,5541 och 0,5671. Slutligen visar vi att den helt online-modellen är strikt svårare än den tidigare modellen eftersom ingen online-algoritm kan vara 0,6317 < 1 – 1 e – konkurrenskraftig i vår modell även för bipartit grafer.
Mycket nyligen, Huang et al. REF föreslog en helt online matchande modell, där alla hörn av grafen anländer online (i godtycklig ordning).
How to match when all vertices arrive online
{'venue': 'STOC 2018', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}