CIS Seminar: “Edge-Weighted Online Bipartite Matching”
/
Wu and Chen Auditorium (Room 101), Levine Hall
3330 Walnut Street, Philadelphia, PA, United States
Online bipartite matching is one of the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) gave an elegant algorithm for unweighted bipartite matching that achieves an optimal competitive ratio 1-1/e. Aggarwal et al. (SODA 2011) later generalized their algorithm and analysis to the vertex-weighted case. Little is known, however, […]

