Events by date

Title: On the Adaptivity Gap of Stochastic Orienteering

Speaker: Paul Lawrence Affiliation: University of Waterloo Location: MC 6029 or contact Rian Neogi for the Zoom link

Abstract: This talk highlights the stochastic orienteering problem, in which we are given a budget B and a graph G=(V,E) with edge distances d(u,v) and a starting vertex x. Each vertex v represents a job with a deterministic reward and a random processing time, drawn from a known distribution.

Title: Bipartite Matching in Almost-Linear Time and More

Speaker: Yang Peng Affiliation: University of Waterloo Location: MC 5501, please contact Amanda Lutz for Zoom link

Abstract:  This talk will present an algorithm that computes maximum bipartite matchings in m^{1 + o(1)} time, and discuss its connections with optimization, graph algorithms, and data structures.