Garantias Melhoradas para Emparelhamento Estocástico Offline por meio de Novos Esquemas de Resolução de Contenção Ordenados

O emparelhamento é um dos problemas mais fundamentais e amplamente aplicáveis em muitos domínios. Nessas diversas aplicações do mundo real, há frequentemente um grau de incerteza na entrada, o que levou ao estudo de modelos de emparelhamento estocástico. Aqui, cada aresta no grafo tem uma probabilidade conhecida e independente de existir, derivada de alguma previsão. Os algoritmos devem explorar as arestas para determinar a existência e emparelhá-las irrevogavelmente se existirem. Além disso, cada vértice pode ter uma restrição de paciência que denota quantas de suas arestas vizinhas podem ser exploradas. Apresentamos novos esquemas de resolução de contenção ordenados que geram garantias de aproximação melhoradas para alguns dos problemas fundamentais estudados nesta área. Para emparelhamento estocástico com restrições de paciência em grafos gerais, fornecemos um algoritmo de aproximação 0.382, melhorando significativamente a melhor aproximação anterior de 0.31. Quando os vértices não têm restrições de paciência, descrevemos um algoritmo de exploração aleatória de ordem 0.432 com vários corolários, como uma garantia melhorada para o problema do Secretário Profeta sob Chegadas de Arestas. Por fim, para o caso especial de grafos bipartidos com restrições de paciência unitárias em uma das partições, mostramos um algoritmo de aproximação 0.632 que melhora um resultado recente que forneceu uma garantia de 1/3. Financiamento: N. Grammel e A. Srinivasan foram apoiados financeiramente em parte pela Divisão de Fundamentos de Computação e Comunicação da National Science Foundation, Prêmio CCF-1749864, e por prêmios de pesquisa da Amazon e do Google.