Online matchning har fått stor uppmärksamhet under de senaste 15 åren på grund av sin nära anslutning till Internet-reklam. Som det seminala arbetet av Karp, Vazirani och Vazirani har ett optimalt (1 - 1/e) konkurrensförhållande i standard kontraarial online-modell, har mycket arbete gjorts för att utveckla användbara online-modeller som införlivar viss stokasticitet i ankomstprocessen. En sådan populär modell är den "kända I.I.D. modell" där olika kundtyper kommer online från en känd distribution. Vi utvecklar algoritmer med förbättrade konkurrensförhållanden för några grundläggande varianter av denna modell med integral ankomsthastigheter, inklusive: a) fallet med allmänna viktade kanter, där vi förbättrar det mest kända förhållandet på 0,667 på grund av Haeupler, Mirrokni och Zadimoghaddam [11] till 0,705; och b) det vertex-viktade fallet, där vi förbättrar 0,7250 förhållandet mellan Jaillet och Lu [12] till 0,7299. Vi överväger också två förlängningar, en är "känd I.I.D." med icke-integral ankomsthastighet och stokastiska belöningar; den andra är "känd I.I.D." b-matchning med icke-integral ankomsthastighet och stokastiska belöningar. Vi presenterar en enkel icke-adaptiv algoritm som fungerar bra samtidigt på de två förlängningarna. En av de viktigaste ingredienserna i vår förbättring är följande (offline) strategi för bipartitmatching polytoper med ytterligare begränsningar. Vi lägger först till flera giltiga begränsningar för att få en bra fraktionerad lösning f; men dessa ger oss mindre kontroll över strukturen av f. Vi tar nästa bort alla dessa ytterligare begränsningar och slumpmässigt flytta från f till en genomförbar punkt på den matchande polytopen med alla koordinater som är från den inställda {0, 1/k, 2/k,. ., 1} för ett valt heltal k. Strukturen av denna lösning är inspirerad av Jaillet och Lu (Mathematics of Operations Research, 2013) och är en dragbar struktur för algoritm design och analys. Den lämpliga slumpmässiga förflyttningen bevarar många av de borttagna begränsningarna (ungefär [exakt] med stor sannolikhet [i förväntan]). Detta ligger till grund för vissa av våra förbättringar, och vi hoppas att det kan vara av oberoende intresse.  ACM Subject Classification F.2 ANALYS AV ALGORITMS OCH PROBLEM COM-PLEXITY Nyckelord och fraser Applications to Internet advertising har drivit studien av online matchningsproblem under de senaste åren [19]. I dessa problem, vi anser en bipartit graf G = (U, V, E) där uppsättningen U är tillgänglig offline medan hörnen i V anländer online. När någon vertex v anländer, måste det matchas omedelbart till högst en vertex i U. Varje offline vertex u kan matchas till högst en v eller i b-matchning generalization, på de flesta b hörn i V. I samband med Internet reklam, U är uppsättningen av annonsörer, V är en uppsättning intryck, och kanterna E definiera intryck som intresserar en viss annonsör. När v anländer måste vi välja en tillgänglig annonsör (om någon) för att matcha med den. Inledningsvis anser vi att fallet där v  på V kan matchas på de flesta en gång. Vi slappnar senare av detta tillstånd till det matchas upp till B gånger. Eftersom reklam är den viktigaste inkomstkällan för många stora Internetföretag, kan hitta bra matchande algoritmer och få även små resultatvinster ha stor inverkan. I den stokastiska kända I.I.D. modell för ankomst, vi ges bipartite grafen i förväg och varje anlända vertex v dras med ersättning från en känd distribution på hörnen i V. Detta fångar det faktum att vi ofta har bakgrundsdata om intrycken och kan förutsäga frekvensen med vilken varje typ av intryck kommer att anlända. Edge-viktad matchning [8] är en allmän modell i samband med reklam: varje annonsör får en viss inkomst för att matchas till en viss typ av intryck. Här hänvisar en typ av intryck till en klass av användare (t.ex. en demografisk grupp) som är intresserade av samma undergrupp av annonser. Ett specialfall av denna modell är vertex-viktad matchning [1], där vikterna endast förknippas med annonsörerna. Med andra ord, en viss annonsör har samma intäkter som genereras för att matcha någon av de användartyper som är intresserade av det. I vissa moderna affärsmodeller genereras inte intäkter vid matchande annonser, utan endast när en användare klickar på annonsen: detta är pay-per-click-modellen. Från bakgrundsdata kan man tilldela sannolikheten för att en viss annons klickas av en typ av användare. Verk inklusive [20], [21] fånga detta begrepp genom att tilldela en sannolikhet till varje kant. Ett gemensamt tema i de flesta av våra strategier är att använda en LP-riktmärke med ytterligare giltiga begränsningar som håller för respektive stokastisk-arrival modeller, i kombination med någon form av beroende avrundning. För läsare som inte känner till dessa problem uppmuntras de att först läsa delar av avsnitt 2 för formella definitioner innan de kommer in i det relaterade arbetet. Studien av online matchning började med det seminala arbetet av Karp, Vazirani, Vazirani [14], där de gav en optimal online-algoritm för en version av den oviktade bipartit matchande problem där hörnen anländer i kontradiktorisk ordning. Därefter har en serie verk studerat olika relaterade modeller. Boken av Mehta [19] ger en detaljerad översikt. Den vertex-viktade versionen av detta problem introducerades av Aggarwal, Goel och Karande [1], där de ger ett optimalt 1 – 1 e förhållande för den kontradiktoriska ankomstmodellen. Den kantviktade inställningen har studerats i den kontradiktoriska modellen av Feldman, Korula, Mirrokni och Muthukrishnan [8], där de överväger en ytterligare avslappning av "fri-disposal". Utöver den kontradiktoriska modellen, studeras dessa problem under namnet stokastisk matchning, där online hörnen antingen anländer i slumpmässig ordning eller ritas I.I.D. från en känd distribution av B. Brubach, K. A. Sankararaman, A. srinivasan och P. Xu 3. Verken [5, 15, 16, 17] studerar bland annat den slumpmässiga ankomstordermodellen; papper inklusive [4, 6, 9, 11, 12, 18] [9] som var de första att slå 1 − 1/e med ett konkurrensförhållande på 0,67 för det oviktade problemet. Detta förbättrades av Manshadi, Gharan och Saberi [18] till 0,705 med en adaptiv algoritm. Dessutom visade de att även i den oviktade varianten med integral ankomsthastigheter, ingen algoritm kan uppnå ett förhållande bättre än 1 - e - 2 - 0.86. Slutligen presenterade Jaillet och Lu [12] en adaptiv algoritm som använde en smart LP för att uppnå 0,725 respektive 1 − 2e −2  och 0,729 för vertex-viktade respektive oviktade problem. Relaterat arbete i Edge-Weighted Setting: För denna modell var Haeupler, Mirrokni, Zadimoghaddam [11] de första att slå 1 − 1/e genom att uppnå ett konkurrensförhållande på 0,667. De använder en diskonterad LP med hårdare begränsningar än den grundläggande matchande LP (en liknande LP kan ses i 2.1) och de använder kraften i två val genom att bygga två matchningar offline för att styra sin online-algoritm. I modellen för b-matchning antar vi att varje vertex u har en enhetlig kapacitet på b, där b är en parameter som i allmänhet är ett stort integralvärde. Modellen av oviktad b-matchning kan ses som ett specialfall av Adwords eller Display Ads. Det finns omfattande litteratur för Adwords eller Display Ads under olika inställningar (se boken av Mehta [19]. I synnerhet [13] visar att deras algoritm BALANS är optimal för online b-matchning under den kontradiktoriska modellen, som uppnår ett förhållande på 1 − 1 (1+1/b) b. I denna tidning anser vi kantvikta b-matchning med stokastiska belöningar under den kända I.I.D. Modell med godtyckliga ankomstpriser. Såvitt vi vet är vi de första som tar hänsyn till denna mycket allmänna modell. Devanur et al [7] gav en algoritm som uppnår ett förhållande på 1 − 1/ 2πk för Adwords-problemet i det okända I.I.D. Anlända modell med kunskap om det optimala budgetutnyttjandet och när budet till budget nyckeltal är som högst 1/k. Lägg märke till att inte ens problemet med allmän kantvägd b-matchning med deterministiska belöningar inte kan fångas i Adwords-modellen. Alaei et al [2] anser profeten-Ojämlikhet Matchning problem, där v anländer från en distinkt (känd) distribution D t, i varje omgång t. De gav en 1 − 1/ k + 3 konkurrenskraftig algoritm, där k är den minsta kapaciteten av u. De antar dock deterministiska belöningar, och det är icke-trivialt att utvidga sitt resultat till den stokastiska belöningsinställningen. I detta dokument presenterar vi en mycket enkel algoritm som uppnår ett förhållande på 2 /3 ) för varje given > 0. Det är värt att se att vår algoritm (10) kan trivialt utvidgas till fallet där varje vertex u har en distinkt kapacitet b u. Värdet av b i den slutliga kvoten skulle ersättas av min u på u. I den Oviktade Online Känd I.I.D. Stochastic Bipartite Matching problem, vi får en bipartit graf G = (U, V, E). Setet U är tillgängligt offline medan hörnen v anländer 4 nya algoritmer, Better Bounds, och en ny modell för Online Stochastic Matching online och dras med ersättning från en I.I.D. fördelning på V. För varje v  på V, Vi får en ankomsthastighet r v, Vilket är det förväntade antalet gånger v kommer att anlända. Med undantag för avsnitten 5 och 6 kommer detta dokument att fokusera på den integral-arrival-satser inställning där alla r v  på Z +. Som beskrivs i [11], WLOG vi kan anta i denna inställning att  på v V, r v = 1. Låt n = v på v v vara det förväntade antalet hörn som anländer under online-fasen. I den vertex-viktade varianten, har varje vertex u U en vikt w u och vi söker en maximal vikt matchning. I den kantviktade varianten har varje kant e E en vikt w e och vi söker en maximal viktmatchning. I stokastiska belöningar variant 1, Dessutom har varje kant en sannolikhet p e och vi försöker maximera den förväntade vikten av matchningen. I b-matchning modellen kan varje vertex i U matchas upp till b gånger. Hela tiden kommer vi att använda "WS" för att hänvisa till det värsta fallet för olika algoritmer. Aymptotic antagande och notation: Vi kommer alltid att anta att n är stor och analysera algoritmer som n går till oändlighet: t.ex., om n, Vi kommer bara att skriva detta som "x ≤ 1 − 1/e 2" istället för den mer exakta "x ≤ 1 − 1/e 2 + o(1)". Dessa undertryckta o(1) termer kommer att subtrahera högst o(1) från våra konkurrensförhållanden. En annan sak att notera är att konkurrensförhållandet definieras något annorlunda än vanligt, för denna uppsättning problem (liknar den notation som används i [19]. I synnerhet definieras det som. Algoritmer kan vara adaptiva eller icke adaptiva. När v anländer kan en adaptiv algoritm kontrollera vilka grannar som fortfarande är tillgängliga för att matchas, men en icke adaptiv algoritm kan inte. Vi kommer att använda följande LP till övre gräns för den optimala offline-lösningen och vägleda vår algoritm. Vi kommer först att visa en LP för den oviktade varianten, sedan beskriva förändringar för vertex-viktade och kantviktade inställningar. Som vanligt har vi en variabel f e för varje kant. Låta  på (w) vara den uppsättning kanter som gränsar till en vertex w  på U V och låt f w = e och (w) f e. Maximera E f e (2.1) under förutsättning att Varianter: Den objektiva funktionen är: maximera u och u (u) f e w u i den vertex-viktade varianten och maximera E f e w e i den kantviktade varianten. Restriktion 2.2 är den matchande begränsningen för hörn i U. Restriktion 2.3 är giltig eftersom varje vertex i V har en ankomsthastighet på 1. Restriktion 2.4 används under [18] och [11]. Det fångar det faktum att det förväntade antalet matcher för någon kant är högst 1 - 1/ e. Detta är 1 Den gränsförverkligande processen är oberoende av varandra. Vid varje steg, algoritmen "känner" kanten. Med sannolikhet pe kanten finns och med återstående sannolikhet det inte. När förverkligandet av en kant bestäms, ändras det inte för resten av algoritmen som gäller för stora n eftersom sannolikheten för att en given vertex inte anländer efter n rundor är 1/e. Restriktion 2.5 liknar den tidigare, men för par av kanter. För två grannar i en given u U, Sannolikheten att ingen av dem anländer är 1/e 2. Därför kan summan av variabler för två olika kanter i u inte överstiga 1 − 1/e 2. Observera att begränsningar 2.4 och 2.5 minskar klyftan mellan den optimala LP-lösningen och prestandan hos den optimala online-algoritmen. Utan begränsningar 2.4 kan vi i allmänhet inte uppnå ett konkurrensförhållande som är bättre än 1–1/e. En viktig utmaning för [12] var att deras speciella LP kunde leda till längd fyra cykler av typ C 1 som visas i figur 1. I själva verket använde de denna cykel för att visa att ingen algoritm kunde utföra bättre än 1 − 2/e 2 + 0,7293 med hjälp av sin LP. De nämnde att strängare LP-begränsningar såsom 2.4 och 2.5 i LP från avsnitt 2 kunde undvika denna flaskhals, men de föreslog inte någon teknik för att använda dem. Observera att lösningen {0, 1/3, 2/3} som produceras av deras LP var en viktig komponent i deras Random List-algoritm. Vi visar en randomiserad avrundning algoritm för att konstruera en liknande, förenklad {0, 1/3, 2/3} vektor från lösningen av en strängare referens LP. Detta gör det möjligt att införa ytterligare begränsningar, framför allt begränsningar 2.5. Med hjälp av denna avrundningsalgoritm kombinerad med hårdare begränsningar, kommer vi övre gränsen för sannolikheten för en vertex som visas i cykeln C 1 från figur 1 vid 2−3/e  och 0,89. (Se Lemma 8) Dessutom visar vi hur man deterministiskt bryter alla andra längd fyra cykler som inte är av typ C 1 utan att skapa några nya cykler av typ C 1. Slutligen beskriver vi en algoritm som använder dessa tekniker för att förbättra tidigare resultat i både vertex-viktade och oviktade inställningar. För denna algoritm löser vi först LP i Avsnitt 2 på inmatningskurvan. I avsnitt 4 visar vi hur man använder tekniken i underavsnitt 2.6 för att erhålla en gles fraktionerad vektor. Vi presenterar sedan en randomiserad onlinealgoritm (liknar den i [12]) som använder den glesa fraktionerade vektorn som en guide för att uppnå ett konkurrenskraftigt förhållande på 0,7299. Tidigare fanns det ett gap mellan den bästa oviktade algoritmen med ett förhållande på 1 − 2e − 2 på grund av [12] och det negativa resultatet på 1 − e − 2 på grund av [18]. Vi tar ett steg mot att minska den klyftan genom att visa att en algoritm kan uppnå 0,7299 > 1 − 2e −2 för både oviktade och vertex-viktade varianter med integrerad ankomsthastighet. En utmaning som uppstår i att tillämpa kraften i två val till denna inställning är när samma kant (u, v) ingår i båda matchningar M 1 och M 2. I detta fall, kopia av (u, v) Nya Algoritmer, Better Bounds, och en ny modell för Online Stochastic Matching kan erbjuda ingen nytta och en andra ankomst av v slösas bort. För att använda ett exempel från relaterat arbete, Haeupler et al. [11] Välj två matchningar på följande sätt. M 1 uppnås genom att lösa en LP med begränsningar 2.2, 2.3 och 2.4 och avrundning till en integrerad lösning. M 2 är konstruerad genom att hitta en maximal vikt matchning och ta bort eventuella kanter som redan har inkluderats i M 1. En viktig del av deras bevis visar att sannolikheten för att en kant tas bort från M 2 är högst 1 − 1/e 0.63. Tillvägagångssättet i detta dokument är att konstruera två eller tre matchningar tillsammans på ett korrelerat sätt för att minska sannolikheten för att någon kant ingår i alla matchningar. Vi kommer att visa en allmän teknik för att konstruera en beställd uppsättning k matchningar där k är en lätt justerbar parameter. För k = 2, visar vi att sannolikheten för en kant som visas i både M 1 och M 2 är högst 1 − 2/e  på 0,26. För de algoritmer som presenteras löser vi först en LP på inmatningsgrafen. Vi rundar sedan LP-lösningen vektorn till en gles integral vektor och använder denna vektor för att konstruera en slumpmässigt ordnad uppsättning matchningar som kommer att vägleda vår algoritm under online-fasen. Vi börjar Avsnitt 3 med en enkel uppvärmning algoritm som använder en uppsättning av två matchningar som en guide för att uppnå en 0,688 konkurrensförhållande, förbättra det mest kända resultatet för detta problem. Vi följer upp det med en liten variation som förbättrar förhållandet till 0,7 och en mer komplex 0.705-kompetitiv algoritm som bygger på en konvex kombination av en 3-matchande algoritm och en separat pseudomatchande algoritm. Denna algoritm presenteras i Avsnitt 5. Vi tror på det kända I.I.D. Modell med stokastiska belöningar är en intressant ny riktning som motiveras av arbetet med [20] och [21] i den kontradiktoriska modellen. Vi introducerar en ny, mer allmän LP speciellt för denna inställning och visar att en enkel algoritm som använder LP-lösningen direkt kan uppnå ett konkurrensförhållande på 1 − 1/e. I [21], Det visas att ingen randomiserad algoritm kan uppnå ett förhållande bättre än 0,62 < 1 - 1/e i den kontradiktoriska modellen. Därför att uppnå en 1 - 1 e för i. i. d. Modellen visar att denna nedre gräns inte sträcker sig till denna modell. I Avsnitt 6, vi utvidga denna enkla algoritm 2 till b-matchning generalisering av detta problem där varje offline vertex u kan matcha med upp till b anländer hörn. Vi visar att vår algoritm uppnår ett konkurrensförhållande på minst 2/3 ) för varje given > 0. Observera att detta resultat gör framsteg med öppen fråga 14 i online-matchnings- och annonstilldelningsundersökningen [19], där man frågar om stokastiska belöningar i icke-adversariska modeller. Teorin 1. För vertex-viktad online stokastisk matchning med integral ankomsthastigheter, online algoritm VW uppnår ett konkurrenskraftigt förhållande på minst 0,7299. 2 Nyligen har vi fått veta att resultatet i avsnitt 6 kan erhållas som ett specialfall av [3]. Vårt tillvägagångssätt ger ett alternativ och en enklare algoritm för detta specialfall.  2/3 ) för varje givet > 0. För de algoritmer som presenteras, kommer vi först att lösa referens LP i underavsnitt 2.1 för input instans för att få en fraktionerad lösning vektor f. Vi rundar sedan f till en integrerad lösning F med hjälp av en tvåstegsprocess som vi kallar DR [f, k]. Det första steget är att multiplicera f med k. Det andra steget är att tillämpa de beroende avrundning teknikerna Gandhi, Khuller, Parthasarathy och srinivasan [10] på denna nya vektor. I det här dokumentet väljer vi alltid att k ska vara 2 eller 3. Detta kommer att hjälpa oss att hantera det faktum att en vertex i V kan visas mer än en gång, men förmodligen inte mer än två eller tre gånger. Medan beroende avrundning vanligtvis tillämpas på värden mellan 0 och 1, de användbara egenskaper sträcker sig naturligt till vårt fall där kf e kan vara större än 1 för någon kant e. För att förstå denna process, är det enklast att tänka sig att dela varje kf e i två kanter med heltalsvärdet f e = kf e och fraktionerat värde f e = kf e − kf e. Den förra kommer att förbli oförändrad av den beroende avrundning eftersom det redan är ett heltal medan den senare kommer att avrundas till 1 med sannolikhet f e och 0 annars. Vårt slutliga värde F e skulle vara summan av dessa två avrundade värden. De två egenskaper beroende avrundning som vi kommer att använda är: För alla vertex w  på U V, låt dess fraktionerade grad kf w vara e och (w) kf e och integral grad vara den slumpmässiga variabeln F w = e och (w) F e. Sedan F w... { kf w, kf w }. Edge-viktad matchning med integrerade ankomsthastigheter 3.1 En enkel 0,688-kompetitiv algoritm Som uppvärmning kommer vi att beskriva en enkel algoritm som uppnår ett konkurrenskraftigt förhållande på 0,688 och introducerar nyckelidéer i vår strategi. Vi börjar med att lösa LP i underavsnitt 2.1 för att få en fraktionerad lösning vektor f och tillämpa DR[f, 2] som beskrivs i underavsnitt 2.6 för att få en integrerad vektor F. Vi konstruerar en bipartit graf G F med F e kopior av varje kant e. Observera att G F kommer att ha max grad 2 eftersom för alla w  på U V, F w ≤ 2f w ≤ 2 och därför kan vi dekomponera den i två matchningar med Hall's Theorem.  när v anländer för andra gången, försök att tilldela v till några u 2 om (u 2, v) M 2. 6 När en vertex v anländer för tredje gången eller mer, gör ingenting i det steget. Vi kommer att visa att EW 0 (Algoritm 1) uppnår ett konkurrensförhållande på 0,688. Låt [M 1, M 2 ] vara våra slumpmässigt beställda par av matchningar. Observera att det kan finnas någon kant e som visas i båda matchningarna om f e > 1/2. Därför överväger vi tre typer av kanter. Vi säger en kant e är av typ  på 1, betecknad av e  på 1, Iff e visas endast i M 1. På samma sätt e  på 2, iff e visas endast i M 2 och e b, iff e visas i både M 1 och M 2. Låta P 1, P 2, P b vara sannolikheten för att bli matchad för e  på 1, e  på 2, och e  på b respektive. Enligt resultatet i Haeupler et al. [11], visas respektive värden enligt följande. Det kan finnas högst en kopia av e i G F och sannolikheten för att inkludera e i G F är 2f e. Eftersom en kant i G F kan visas i antingen M 1 eller M 2 med samma sannolikhet 1/2, har vi Pr[e  på 1 ] = Pr[e  på 2 ] = f e. Således är förhållandet (f e P 1 + f e P 2 ) / f e = P 1 + P 2 = 0,729. (1/2)(1−(2f e −1)) = 1−f e. Således är förhållandet (1—f e )(P 1 +P 2 )+(2f e −1)P b )/f e ≥ 0,688, där WS är för en kant e med f = 1 −1/e. 2. Utgångspunkten är följande: I detta avsnitt beskriver vi en förbättring av den tidigare uppvärmningsalgoritmen för att få ett konkurrensförhållande på 0,7. Vi börjar med att göra en observation om prestandan hos uppvärmningsalgoritmen. Efter att ha löst LP, låt kanterna med f e > 1/2 kallas stora och kanter med f e ≤ 1/2 kallas små. Låt L och S, vara uppsättningar av stora och små kanter, respektive. Notera att i den tidigare analysen uppnådde små kanter ett mycket högre konkurrensförhållande på 0,729 jämfört med 0,688 för stora kanter. Detta beror främst på att vi kan få två kopior av en stor kant i G F. I detta fall, kopian i M 1 har en bättre chans att matchas, eftersom det inte finns någon kant som kan blockera det, men den kopia som är i M 2 har ingen chans att matchas. För att korrigera denna obalans gör vi en ytterligare ändring av f e-värdena innan vi tillämpar DR [f, k]. Resten av algoritmen är exakt densamma. Låt η vara en parameter som ska optimeras senare. För alla stora kanter så att f > 1/2, vi sätter f = f + η. För alla små kanter som ligger i anslutning till någon stor kant, låt L vara den största kanten i anslutning till s sådan att f > 1/2. Observera att det är möjligt för e att ha två stora grannar, men vi bryr oss bara om den största. Vi sätter f s = f s Med andra ord ökar vi värdena på stora kanter samtidigt som vi ser till att för alla w  på U V, f w ≤ 1 genom att minska värdena på angränsande små kanter proportionellt mot deras ursprungliga värden. Observera att det inte är möjligt för två stora kanter att vara intilliggande eftersom de båda måste ha fe > 1/2. För alla andra små kanter som inte gränsar till några stora kanter, lämnar vi deras värden oförändrade. Vi applicerar sedan DR[f, 2] på denna nya vektor, multiplicerar med 2 och tillämpar beroende avrundning som tidigare. Vi kan nu bevisa Theorem 2. Bevis. Som i uppvärmningsanalysen, kommer vi att överväga stora och små kanter separat Här har vi två fall Case 1: s är inte i närheten av några stora kanter. I detta fall är analysen densamma som uppvärmningsalgoritmen och vi får fortfarande ett 0,729 konkurrenskraftigt förhållande för dessa kanter. Fall 2: s ligger i anslutning till några stora kanten. För detta fall, låt f vara värdet av den största angränsande kanten i den ursprungliga LP-lösningen. Sedan får s ett förhållande av nya algoritmer, bättre band, och en ny modell för online stokastisk matchning Observera att för f. [0, 1) är detta en minskande funktion med avseende på f. Så det värsta fallet är f = 1 − 1/e och vi har ett förhållande på 1 − (1 − 1/e + η) 1 − (1 − 1/e) (0,1484 + 0,5803) = 1/e − η 1/e (0,1484 + 0,5803) e : Här är förhållandet (1 – (f + η))(P 1 + P 2 ) + (2 (f + η) − 1)P b )/f, där WS är för en kant med f = 1 − 1/e eftersom detta är en minskande funktion med avseende på f. Välj det optimala värdet av η = 0,0142, ger en total konkurrenskvot på 0,7 för denna nya algoritm. I de följande avsnitten kommer vi att beskriva vår slutliga algoritm, med alla dämpningsfaktorer. För att hålla den modulär ger vi följande guide till läsaren. 3.3.1 Beskrivning av huvudalgoritmen som internt åberopar två algoritmer EW 1 och EW 2 som beskrivs i avsnitt 3.3.2 respektive 3.3.3. Teorem 2 visar det slutliga konkurrensförhållandet. Detta bevis beror på prestandagarantierna för EW 1 och EW 2, som ges av Lemmas 6 respektive 7. Bevis på Lemma 6 beror på fordringar 15, 16 och 17 (se bilagan). Var och en av dessa påståenden är en noggrann analys från fall till fall. Intuitivt, 15 avser fallet där u har en stor kant och en liten kant (här analys är för den stora kanten), 16 avser fallet där u är incident till tre små kanter och 17 hänvisar till fallet där u är incident till en liten kant och stor kant (här analysen är för den lilla kanten). Bevis på Lemma 7 beror på fordringar 18 och 19 (se bilagan). Båda dessa påståenden bevisas återigen genom en noggrann analys från fall till fall. Eftersom det finns många fall, har vi gett ett diagram över fallen när vi bevisar dem. I detta avsnitt kommer vi att beskriva en algoritm EW (Algoritm 2), som uppnår ett konkurrensförhållande på 0,705. Algoritmen löser först referens LP i underavsnitt 2.1 och får en fraktionerad optimal lösning f. Genom att åberopa DR[f, 3] får den en slumpmässig integrerad lösning F. Observera att från LP begränsning 2.4 ser vi f e ≤ 1 − 1/e ≤ 2/3. Därför efter DR[f, 3], var och en F e... {0, 1, 2}. Betrakta grafen G F där varje kant e är associerad med värdet av F e. Vi säger en kant e är stor om F e = 2 och liten om F e = 1 (observera att detta skiljer sig från definitionen av stora och små i föregående underavsnitt). Vi designar två icke-adaptiva algoritmer, betecknade som EW 1 och EW 2, som tar den glesa grafen G F som ingång. Skillnaden mellan de två algoritmerna EW 1 och EW 2 är att EW 1 gynnar de små kanterna medan EW 2 gynnar de stora kanterna. Den slutliga algoritmen är att ta en konvex kombination av EW 1 och EW 2 d.v.s. Kör EW 1 med sannolikhet q och EW 2 med sannolikhet 1 − q. B. Brubach, K. A. Sankararaman, A. Srinivasan och P. Xu 11 1 Lös referens LP i underavsnitt 2.1 för indata. Låt f vara den optimala lösning vektorn. 2 Invoke DR[f, 3] för att erhålla vektorn F. 3 Självständigt köra EW 1 och EW 2 med sannolikheter q och 1 − q respektive på G F. Detaljerna för algoritm EW 1 och EW 2 och beviset för Theorem 2 presenteras i följande avsnitt. I detta avsnitt beskriver vi den randomiserade algoritmen EW 1 (Algoritm 3). Antag att vi visar grafen av G F på ett annat sätt där varje kant har F e kopior. Låt PM [F, 3] hänvisa till processen för att bygga grafen G F med F e kopior av varje kant, sönderdela den i tre matchningar, och slumpmässigt permutera matchningarna. EW 1 åberopar först PM[F, 3] för att erhålla en slumpmässig beställd trippel av matchningar, säger [M 1, M 2, M 3 ]. Observera att från LP-restriktionen 2.4 och egenskaperna hos DR[f, 3] och PM [F, 3] kommer en kant att visas i högst två av de tre matchningarna. För en liten kant e = (u, v) i G F, säger vi e är av typ 1 om u har två andra grannar v 1 och v 2 i G F med F (u,v1) = F (u,v2) = 1. Vi säger att e är av typ 2 om u har exakt en annan granne v 1 med F (u,v1) = 2. WLOG vi kan anta att för varje u, F u = e på (u) F e = 3; annars kan vi lägga till en dummy nod v till grannskapet av u. Observera att vi använder terminologin, tilldela v till u för att beteckna att kanten (u, v) matchas av algoritmen om u inte matchas förrän det steget. 1 Anropa PM[F, 3] för att erhålla en slumpmässig beställt trippel matchningar, säger [M 1, M 2, M 3 ]. 2 När en vertex v kommer för första gången, tilldela v till några u 1 med (u 1, v) M 1. 3 När v kommer för andra gången, tilldela v till några u 2 med (u 2, v) M 2. 4 När v kommer för tredje gången, om e är antingen en stor kant eller en liten kant av typ 1 sedan tilldela v till några u 3 med e = (u 3, v) M 3. Men om e är en liten kant av typ 2 sedan med sannolikhet h, tilldela v till några u 3 med e = (u 3, v) M 3; annars, gör ingenting. 5 När v kommer för fjärde eller mer tid, gör ingenting i det steget. Här, h är en parameter som vi kommer att fixa i slutet av analysen. Låt R[EW 1, 1/3] och R[EW 1, 2/3] vara konkurrensförhållandet för en liten kant respektive stor kant. Bevis. I händelse av den stora kanten e, vi delar analysen i tre fall där varje fall motsvarar e i en av de tre matchningar. Och vi kombinerar dessa villkorliga sannolikheter med Bayes' teorem för att få den slutliga konkurrensförhållandet för e. För var och en av de två typerna av små kanter, vi villkorar dem på samma sätt baserat på matchningen de kan visas 12 nya algoritmer, bättre gränser, och en ny modell för Online Stochastic Matching i, och kombinera dem med Bayes' teorem. Fullständigt bevis finns i avsnitt A.1.1 i tillägget. EW 2 (Algoritm 5) är en icke-adaptiv algoritm som tar G F som ingång och presterar bra på de stora kanterna. Kom ihåg att den tidigare algoritmen, EW 1, först åberopar PM[F, 3] för att erhålla en slumpmässig beställd trippel av matchningar. EW 2 kommer däremot att åberopa en rutin, betecknad som PM * [F, 2] (Algoritm 4), för att generera ett (random beställd) par pseudo-matchningar från F. Kom ihåg att F är en integrerad lösning vektor där e F e  till {0, 1, 2}. WLOG, vi kan anta att F v = 1 för varje v i G F. Ta en slumpmässig permutation av ∂(v), säg (π 1, π 2, π 3 ). Lägg till π 1 till M 1 med sannolikhet y 1 och π 2 till M 2 med sannolikhet y 2. Här 0 ≤ y 1, y 2 ≤ 1 är parametrar som kommer att fastställas efter analysen. Algoritm 5 beskriver EW 2. Bevis. Vi analyserar detta från fall till fall genom att överväga det lokala området i utkanten. En stor kant kan ha två möjliga fall i sitt grannskap, medan en liten kant kan ha åtta möjliga fall. Att välja det värsta fallet bland de två för stor kant och det värsta fallet bland de åtta för den lilla kanten, vi bevisa påståendet. Fullständiga uppgifter om beviset finns i avsnitt A.1.2 i tillägget. I detta avsnitt kommer vi att bevisa teorem 2. Bevis. Låta (a 1, b 1 ) vara de konkurrensförhållanden som uppnås genom EW 1 för stora och små kanter, respektive. På samma sätt, låt (a 2, b 2 ) betecknar samma för EW 2. Vi kommer att ha följande två fall.  Konvexkombinationens konkurrensförhållande maximeras vid q = 0,149251 med ett värde på 0,70546. I detta avsnitt kommer vi att överväga vertex-viktade online stokastisk matchning på en bipartit graf G under kända I.I.D. Modell med integral ankomstpriser. Vi kommer att presentera en algoritm där varje u har ett konkurrensförhållande på minst 0,72998. Kom ihåg att efter att ha åberopat DR[f, 3] kan vi få en (slumpmässig) integral vektor F med F e 0, 1, 2}. Definiera H = F/3 och låt G H vara den graf som induceras av H och varje kant tar värdet H e  till {0, 1/3, 2/3}. I detta avsnitt fokuserar vi på den glesa grafen G H. De viktigaste stegen i algoritmen är: 1. Lös den vertex-vägda referens LP i underavsnitt 2.1. Låt f vara en optimal lösning vektor. Anropa DR[f, 3] för att erhålla en integrerad vektor F och en fraktionerad vektor H med H = F/3. Applicera en rad ändringar i H och omvandla den till en annan lösning H. Se underavsnitt 4.1. Kör den randomiserade listan algoritm (RLA) [12] inducerad av H på grafen G H. Vårt mål är att generera en distribution över Π(∂(v)), som betecknar uppsättningen av alla permutationer av noder incident till u. Här hänvisar vi till en permutation av alla noder incident till u som en slumpmässig lista R v. Låt H u = v.u H (u,v) (u2,v). Antag att v har tre grannar i G H. Ta sedan en slumpmässig permutation ( Den resulterande slumpvisa listan Algoritm RLA [H], visas i Algoritm 6. Den WS för vertex-viktat fall i [12] visas i figur 2, som kom fram till node u med ett konkurrensförhållande på 0,725. Enligt deras analys har node u 1 ett konkurrensförhållande på minst 0,736. Därför ökar vi prestanda u på bekostnad av u 1. Med andra ord ökar vi värdet av H (u,v1) och minskar värdet H (u1,v1). Fall (10) och (11) i figur 4 illustrerar detta. Efter denna ändring är den nya WS för vertex-viktad nu den C 1 cykel som visas i figur 1. Detta är faktiskt WS för det oviktade fallet [12]. Lemma 8 och cykelbrytningsalgoritmen innebär dock att C 1-cykeln med sannolikhet kan undvikas minst 3/e − 1. Detta hjälper oss att förbättra förhållandet även för det oviktade fallet [12]. - Lemma 8. - Vad är det? För varje givet u  på U visas i en C 1-cykel efter DR[f, 3] med sannolikhet högst 2 − 3/e. Bevis. Tänk på grafen G H som erhålls efter DR [f, 3]. Observera att för att vissa vertex u ska visas i en C 1-cykel, måste den ha en angränsande kant med H e = 2/3. Nu försöker vi begränsa sannolikheten för den här händelsen. Det är lätt att se att för vissa e e  på (u) med f e ≤ 1/3, F e ≤ 1 efter DR [f, 3] och därmed H e = F e /3 ≤ 1/3. På så sätt kommer endast de kanter som är tillgängliga för fe > 1/3 att avrundas till H e = 2/3. Observera att det kan finnas högst två sådana kanter i  ska(u), eftersom e ska(u) f e ≤ 1. Därför har vi följande två fall. (u) innehåller endast en kant e med f e > 1/3. Låt märka att q 1 + q 2 = 1 och därmed q 2 = 3f e − 1. Eftersom detta är en ökande funktion av f e och f e ≤ 1 − 1/e från LP restriktion 2.4, har vi q 2 ≤ 3 (1 − 1/e) − 1 = 2 − 3/e. innehåller två kanter e 1 och e 2 med f e1 > 1/3 och f e2 > 1/3. Låt q 2 vara sannolikheten att efter DR[f, 3] antingen H e1 = 2/3 eller H e2 = 2/3. Observera att dessa två händelser utesluter varandra eftersom H u ≤ 1. Med hjälp av analysen från fall 1 följer att q 2 = (3f e1 − 1) + (3f e2 − 1) = 3f e1 + f e2 ) − 2. Från LP restriktion 2.5, vi vet att f e1 +f e2 ≤ 1‐1/e 2, och därmed q 2 ≤ 3 (1‐1/e 2 )‐2 < 2 − 3/e. Algoritm 7: [Cykel bryta algoritm] Offline fas 1 Medan det finns någon cykel av typ C 2 eller C 3, Gör: 2 Bryt alla cykler av typ C 2. 3 Bryt en cykel av typ C 3 och återgå till det första steget. Den första ändringen är att bryta cyklerna deterministiskt. Det finns tre möjliga cykler av längd 4 i grafen G H, betecknade C 1, C 2, och C 3. I [12], de ger ett effektivt sätt att bryta C 2 och C 3, som visas i figur 2. Cykel C 1 kan inte ändras ytterligare och därför är flaskhalsen för deras oviktade fall. Lägg märke till att samtidigt bryta cyklerna av C 2 och C 3, nya cykler av C 1 kan skapas i grafen. Eftersom vår randomiserade konstruktion av lösning H ger oss kontroll över sannolikheten för att cykler C 1 inträffar, skulle vi vilja bryta C 2 och C 3 på ett kontrollerat sätt, för att inte skapa några nya C 1 cykler. Detta förfarande sammanfattas i algoritm 7. Beviset för Lemma 12 följer av följande påståenden: Påstående 9. Brytcykler kommer inte att ändra värdet H w för någon w  på U V. Påstående 10. Efter att ha brutit en cykel av typ C 2, hörn u 1, u 2, v 1, och v 2 kan aldrig vara en del av någon längd fyra cykel. Påstående 11. När alla längd fyra cykler är av typ C 1 eller C 3, bryta exakt en cykel av typ C 3 kan inte skapa en ny cykel av typ C 1. Nya algoritmer, bättre gränser, och en ny modell för Online Stochastic Matching Proof. Som visas i figur 2, Vi ökar och minska kanten värden f e på ett sådant sätt att deras belopp H w vid någon vertex w kommer att bevaras. Observera att C 2 cykler kan brytas fritt utan att skapa nya C 1 cykler. Efter att ha tagit bort alla cykler av typ C 2, Ta bort en enda cykel av typ C 3 kan inte skapa några cykler av typ C 1. Algoritm 7 avlägsnar därför alla C 2 och C 3 cykler utan att skapa några nya C 1 cykler. Bevis. Tänk på strukturen efter att bryta en cykel av typ C 2. Observera att kanten (u 2, v 2 ) har permanent tagits bort och därmed dessa fyra hörn tillsammans kan aldrig vara en del av en cykel av längd fyra. Vertikerna u 1 och v 1 har H u1 = 1 respektive H v1 = 1. Så de kan inte ha några andra kanter och därför inte visas i någon längd fyra cykel. Vertices u 2 och v 2 kan var och en ha en ytterligare kant, men eftersom kanten (u 2, v 2 ) har tagits bort, de kan aldrig vara en del av någon cykel med längd mindre än sex. Bevis. För det första noterar vi att eftersom inga kanter kommer att läggas till under denna process, kan vi inte skapa en ny cykel av längd fyra eller gå med en cykel av typ C 1. Därför är de enda cykler som kan påverkas av typ C 3. Men varje cykel c av typ C 3 faller i ett av två fall Fall 1: c är den cykel vi bryter. I detta fall kan c inte bli en cykel av typ C 1 eftersom vi tar bort två av dess kanter och bryta cykeln. Fall 2: c är inte den cykel vi bryter. I detta fall kan c ha högst en av sina kanter omvandlas till en 2/3 kant. Låt c vara längden fyra cykel vi bryter. Observera att c och c skiljer sig åt med minst en vertex. När vi bryter c, De två kanterna som omvandlas till 2/3 kommer att täcka alla fyra hörn av c. Därför kan som mest en av dessa kanter vara i c. Observera att bryta en cykel av typ C 3 kan skapa cykler av typ C 2, Men dessa cykler alltid bryts i nästa iteration, innan bryta en annan cykel av typ C 3. Det här är Lemma 12. Efter att ha tillämpat Algoritm 7 till G H, Vi har (1) värdet H w är bevarad för varje w  på U V ; (2) Informellt, denna andra ändring minskar frekvensen av listor som förknippas med dessa noder u med H u = 1/3 eller H u = 2/3 och ökar antalet listor associerade med noder u med H u = 1. Vi ska illustrera detta med följande exempel. Betrakta grafen G i figur 3. Låt tunna och tjocka kanter representera H e = 1/3 och H e = 2/3. Vi kommer nu att beräkna konkurrensförhållandet efter att tillämpa RLA på G. Låt P u betecknar sannolikheten att u matchas efter algoritmen. Låt B u betecknar händelsen som bland n slumpvisa listor, det finns en lista som börjar med u och G v u betecknar händelsen som bland n listor, det finns på varandra följande listor sådan att (1) Var och en av dessa listor börjar med en u = u och u  på u (v) och (2) Listorna anländer i en ordning som säkerställer att u matchas av algoritmen. Från lemma 4 och Corollary 1 i [12] följer följande lemma: Lemma 13. Antag att u inte är en del av någon cykel av längd 4. Vi har För noden u, vi har Pr [B u u är händelsen att bland n listor, den slumpmässiga listan R v1 = (u 1, u) kommer minst två gånger. Observera att listan R v1 = (u 1, u) kommer med sannolikhet Intuitivt, kan man förbättra det värsta fallet förhållandet genom att öka ankomsthastigheten för R v1 = (u, u 1 ) samtidigt minska det för R v1 = (u 1, u). Antag att man ändrar H (u1,v1) och H (u,v1) till H (u1,v1) = 0,1 och H (u,v1) = 0,9, ankomsthastigheten för R v1 = (u, u 1 ) och R v1 = (u 1, u) ändras till 0,1/n respektive 0,9/n. De resulterande förändringarna är Pr[B u ] = 1 − e −0.9−1/3, Pr[G (11) och (12) hjälpa till att förbättra den WS som beskrivs i figur 2.  Vertex-Weighted Algorithm VW Algoritmen VW består av två olika slumpmässiga processer: sub-rutin DR [f, 3] i offline-fasen och RLA i online-fasen. Analysen består följaktligen av två delar. Först, för en given graf G H, analyserar vi förhållandet mellan RLA[H ] för varje nod u med H u = 1/3, H u = 2/3 och H u = 1. Analysen liknar [12]. För det andra analyserar vi sannolikheten för att DR[f, 3] omvandlar varje u, med fraktionerade f u-värden, till de tre diskreta fall som ses i den första delen. Genom att kombinera resultaten från dessa två delar får vi det slutliga förhållandet. Låt oss först analysera konkurrensförhållandet för RLA [H]. För en given H och G H, låt P u vara sannolikheten att u matchas i RLA [H ]. Observera att värdet P u bestäms inte bara av algoritmen RLA själv, utan också de ändringar som tillämpas på H. Vi definierar beviset. Från Lemmas 8 och 12 vet vi att alla u är närvarande i cykel C 1 med högst sannolikhet (2 − 3/e). Betrakta en nod u med 2/3 ≤ f u ≤ 1 och låt q 1, q 2, q 3 vara sannolikheten att efter DR[ f, 3] och den första ändringen, H u = 1 och u är i den första cykeln C 1, H u = 1 och u är inte i C 1, H u = 2/3 respektive. Från Lemma 14 får vi att den slutliga kvoten för u åtminstone ska minimera ovanstående uttryck under förutsättning att (1) q 1 + q 2 + q 3 = 1; (2) 0 ≤ q i, 1 ≤ i ≤ 3; (3) q 1 ≤ 2 − 3/e, vi får ett minimivärde på 0,729982 för q 1 = 2 − 3/e och q 2 = 3/e − 1. För varje nod u med 0 ≤ u ≤ 2/3, vet vi att förhållandet är minst minvärdet av R[RLA, 2/3] och R[RLA, 1/3], vilket är 0,7622. Detta kompletterar beviset för Theorem 1. Icke-integrerade ankomstpriser med stokastiska belöningar Inställningen här är strikt generaliserad över de föregående avsnitten på följande sätt. För det första tillåter det en godtycklig ankomsthastighet (säg r v ) som kan vara fraktionerad för varje stokastisk vertex v. Observera att v r v = n där n är det totala antalet rundor. För det andra är varje e = (v, u) E associerat med ett värde p e, vilket anger sannolikheten att e = (u, v) är närvarande när vi tilldelar v till u. Vi antar att denna process är oberoende av den stokastiska ankomsten av varje v. Vi kommer att visa att den enkla icke-adaptiva algoritm som infördes i [11] kan utvidgas till detta allmänna fall. Detta ger ett konkurrenskraftigt förhållande (1 − 1 e ). Lägg märke till att Manshadi et al. [18] visar att ingen icke-adaptiv algoritm kan uppnå ett förhållande som är bättre än (1 −1/e) för den icke-integrerade ankomsthastigheten, även för alla p = 1. Därför är vår algoritm en optimal icke-adaptiv algoritm för denna modell. Vi använder en liknande LP som [12] för icke-integrerade ankomstpriser. För varje e E, låt f e vara sannolikheten att e matchas i offline optimal algoritm. Således har vi vår algoritm sammanfattas i Algoritm 9. Observera att den sista begränsningen säkerställer att steg 2 i algoritmen är giltig. Låt oss nu bevisa teorem 3. Algoritm 9: SM 1 Skapa och lösa LP (5.1). WLOG antar att {f e  på E} är en optimal lösning. 2 När en vertex v anländer, tilldela v till var och en av dess granne u med en sannolikhet f (u,v) vv. Bevis. Låt B(u, t) vara den händelse som u är säker i början av runda t och A(u, t) att vara den händelse som vertex u matchas under runda t konditionerade på B (u, t I detta avsnitt, vi ytterligare generalisera modellen i Avsnitt 5 till fallet där varje u i offline uppsättning U har en enhetlig integrerad kapacitet b (dvs, varje vertex u kan matchas på de flesta b gånger). Annars behåller vi samma inställning som i avsnitt 5; vi tillåter icke-integrerade ankomstpriser och stokastiska belöningar. Vi kommer att generalisera den enkla algoritm som används i föregående inställning (dvs., Avsnitt 5) till denna nya inställning. Vi ändrar algoritm 9 för b-matchningsproblemet enligt följande. Algoritm 10: SM b 1 Konstruera och lösa LP (6.1). WLOG antar att {f e  på E} är en optimal lösning. 2 När en vertex v anländer, tilldela v till var och en av dess granne u med en sannolikhet f (u,v) vv. Låt oss nu bevisa Theorem 4. Bevis. Beviset liknar det i Theorem 3. Låt A t vara antalet gånger u har matchats i början av omgången t. Låt B(u, t) vara den händelse som u är säker i början av omgången t, som definieras som At ≤ b − 1. För varje given kant e, låt X e vara antalet gånger som e matchas över n rundorna. (u,v) r v p (u,v) ≤ b n Det följer att för alla t ≤ n(1 − τ ) med 0 < τ < 22 REFERENSER 7 I detta dokument gav vi förbättrade algoritmer för Edge-Weighted och Vertex-Weighted modeller. Tidigare fanns det ett gap mellan den bästa oviktade algoritmen med ett förhållande på 1 − 2e − 2 på grund av [12] och det negativa resultatet på 1 − e − 2 på grund av [18]. Vi tog ett steg mot att minska den klyftan genom att visa att en algoritm kan uppnå 0,7299 > 1 − 2e −2 för både oviktade och vertex-viktade varianter med integrerad ankomsthastighet. Genom att göra det gjorde vi progesser på öppna frågor 3 och 4 i online matchnings- och annonstilldelningsenkäten [19]. Detta var möjligt eftersom vår strategi för avrundning till en enklare bråkdelslösning gjorde det möjligt för oss att använda en strängare LP. För den kantviktade varianten visade vi att man avsevärt kan förbättra kraften i två val genom att generera två matchningar från samma LP-lösning. För varianten med kantvikter, icke-integrerade ankomsthastigheter och stokastiska belöningar presenterade vi en (1 −1/e)-kompetitiv algoritm. Detta visade att de 0,62 < 1 − 1/e som gavs i [21] för den kontradiktoriska modellen med stokastiska belöningar inte sträcker sig till det kända I.I.D. Förlaga. Dessutom ansåg vi att det online kantviktade b-matchning problemet med stokastiska belöningar under den kända IID-inställningen. Vi gav en mycket enkel icke-adaptiv algoritm som uppnår ett förhållande på 1 − b 2 /3 ) för varje given > 0. Ett naturligt nästa steg i den kantviktade inställningen är att använda en adaptiv strategi. För det vertex-viktade problemet kan man lätt se att den strängare LP vi använder fortfarande har en lucka. Dessutom använder vi endast fraktionerade lösningar {0, 1/3, 2/3}. Beroende avrundning ger dock lösningar i {0, 1/k, 2/k,. ., k(1 − 1/e) /k}; möjliggör slumpvisa listor över längd större än tre. Striktare LP och längre listor kan båda ge bättre resultat. I den stokastiska belöningsmodellen med icke-integrerade ankomstpriser, är en öppen fråga att antingen förbättra på 1 - 1 e förhållandet eller överväga en enklare modell med integrerad ankomst priser och förbättra förhållandet för denna begränsade modell. Slutligen finns det en klyfta mellan vårt resultat för b-matchning med stokastiska belöningar och resultaten av [7] och [2] för liknande problem med deterministiska belöningar. Det skulle vara trevligt att se ett resultat för detta problem som är 1 − O(k −1/2 ). Tack:
Hittills har det mest kända konkurrensförhållandet på 0,730 berott på Brubach et al Ref.
New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}