Events by date

Title: Approximation Algorithms for Stochastic Knapsack 

Speaker: David Aleman Affiliation: University of Waterloo Location: MC 6029 or contact Rian Ne

Abstract: The classical Knapsack problem takes as input a set of items with some fixed nonnegative values and weights. The goal is to compute a subset of items of maximum total value, subject to the constraint that the total weight of these elements is at most a given limit. In this talk we review a paper by Gupta, Krishnaswamy, Molinaro and Ravi, in which the following stochastic variation of this problem is considered: the value and weight of each item are correlated random variables with known, arbitrary distributions.

Title: Sylvester, Gallai, and their complex relatives

Speaker: Jim Geelen Affiliation: University of Waterloo Location: MC 5501 or contact Melissa Cambridge for Zoom link

Abstract: Given any finite set of points in the real plane, not all collinear, there is a line in the plane that contains exactly two of them. This pretty result was conjectured by Sylvester in 1893 and proved by Gallai in 1944. We will present an extension of the result to higher dimensional complex spaces and discuss some related conjectures. This is joint work with Matthew Kroeker.