Det stokastiska matchande problemet handlar om att hitta en maximal matchning i en graf vars kanter är okända men kan nås via frågor. Detta är ett speciellt fall av stokastisk k-set förpackning, där problemet är att hitta en maximal förpackning av satser, som var och en finns med viss sannolikhet. I detta dokument ger vi kant och ställa frågealgoritmer för dessa två problem, respektive, som bevisligen uppnår en bråkdel av den allvetande optimala lösningen. Vårt huvudsakliga teoretiska resultat för den stokastiska matchning (dvs. 2-uppsättning packning) problem är utformningen av en adaptiv algoritm som frågar bara ett konstant antal kanter per vertex och uppnår en (1 − ) bråkdel av den allvetande optimal lösning, för en godtyckligt liten > 0. Dessutom utför denna adaptiva algoritm frågorna i bara ett konstant antal rundor. Vi kompletterar detta resultat med en icke-adaptiv (dvs en omgång av frågor) algoritm som uppnår en (0, 5 − ) bråkdel av den allvetande optimal. Vi utökar också både våra resultat till stokastisk k-set förpackning genom att utforma en adaptiv algoritm som uppnår en ( − för deterministiska k-set förpackningsproblem [Fürer och Yu 2013]. Vi utforskar empiriskt tillämpningen av (anpassningar av) dessa algoritmer till njure utbytesproblem, där patienter med slutstadiet njursvikt utbyte villiga men inkompatibla givare. Vi visar på både genererade data och på verkliga data från de första 169 matchkörningar av UNOS rikstäckande njure utbyte att även ett mycket litet antal icke-adaptiva kantfrågor per vertex resulterar i stora vinster i förväntade framgångsrika matcher.
Mer specifikt, Blum et al. REF ger en adaptiv algoritm som uppnår en (1 − ε)- tillnärmning genom att fråga log(2/ε ) p 2/ε pervertex kanter, i samma antal rundor.
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
{'venue': "EC '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}