Title: Approximation algorithms for stochastic orienteeringSpeaker: Madison Van Dyk Affiliation: University of Waterloo Location: MC 6029 or contact Rian Neogi for Zoom link
Abstract: This week we revisit the stochastic orienteering problem in which we are given a metric graph where each node has a deterministic reward and a random size. The goal is to adaptively decide on which nodes to visit to maximize the expected reward, while not exceeding the budget B on the distance plus the size of jobs processed.
Title: Approximating Weighted Connectivity Augmentation below Factor 2Speaker: Vera Traub Affiliation: Research Institute for Discrete Mathematics, University of Bonn Location: MC 5501 or contact Melissa Cambridge for Zoom link
Abstract: The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no better-than-2 approximation algorithm has been known, whereas 2-approximations can be easily obtained through a variety of well-known techniques.