Events by date

Title: Approximation algorithms for stochastic orienteering  

Speaker: 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 2

Speaker: 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.