Title: A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints, Part IISpeaker: Noah Weninger Affiliation: University of Waterloo Location: MC 6029
Abstract: We consider the bilevel knapsack problem with interdiction constraints, a generalization of 0-1 knapsack. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack (i.e. interdict) such that the maximum profit attainable from packing the remaining items into the second knapsack is minimized.
Title: An Approximate Generalization of the Okamura-Seymour TheoremSpeaker: Nikhil Kumar Affiliation: University of Waterloo Location: MC 5501
Abstract: We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands.