Vi anser att den maximala bipartit matchande problem i stokastiska inställningar, nämligen fråge-commit och pris-of-information modeller. I frågetecken modell, en kant e oberoende existerar med sannolikhet p e. Vi kan fråga om en kant finns eller inte, men om det finns, då måste vi ta det till vår lösning. I det oviktade fallet kan man fråga kanter i den ordning som ges av den klassiska online-algoritmen Karp, Vazirani och Vazirani [KVV90] för att få en (1 −1/e)-uppskattning. Däremot är den tidigare mest kända algoritmen i det viktade fallet den (1/2)-uppskattning som uppnås av den giriga algoritmen som sorterar kanterna efter deras vikter och frågor i den ordningen. Genom att förbättra den grundläggande giriga ger vi en (1 −1/e) approximationsalgoritm i den viktade frågeteckensmodellen. Vi använder ett linjärt program (LP) till övre gräns den optimala uppnås genom någon strategi. Den föreslagna LP medger flera strukturella egenskaper som spelar en avgörande roll i utformningen och analysen av vår algoritm. Vi utökar också dessa tekniker för att få en (1 − 1/e) - approximation algoritm för maximal bipartite matchning i pris-of information modell som infördes av Singla [Sin18], som också använde den grundläggande giriga algoritmen för att ge en (1/2) - approximation.
Gamlath et al. REF tillhandahöll en 1-1 e-konkurrensalgoritm för den viktade versionen av detta problem.
Beating Greedy for Stochastic Bipartite Matching
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}