Mahsa Derakhshan, University of California, Berkeley

Abstract

In this talk, we discuss the max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We will present polynomial-time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc. 

In the vertex arrival version of the problem, the goal is to find an approximate max-weight matching of a given bipartite graph when the vertices in one part of the graph arrive online in a fixed order with independent chances of failure. Whenever a vertex arrives, we should decide, irrevocably, whether to match it with one of its unmatched neighbors or leave it unmatched forever.  There has been a long line of work designing approximation algorithms for different variants of this problem with respect to the offline benchmark (prophet). Papadimitriou et al., however, propose the alternative {em online} benchmark and show that considering this new benchmark allows them to improve the $0.5$ approximation ratio, which is the best ratio achievable with respect to the offline benchmark. They provide a $0.51$-approximation algorithm which was later improved to $0.526$ by Saberi and Wajc. In this talk, we mainly discuss our recent algorithm with a significantly improved approximation ratio of $(1-1/e)$ for this problem

We also consider the edge arrival version in which, instead of vertices, edges of the graph arrive online with independent chances of failure. Designing approximation algorithms for this problem has also been studied extensively, with the best approximation ratio being $0.337$ with respect to the offline benchmark. In this talk, we also present a simple algorithm with an approximation ratio of $0.5$ against the online benchmark. 

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar