Title: A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction ConstraintsSpeaker: 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. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments for 99% of the instances reported in the literature.
Title: Proof of the Clustered Hadwiger ConjectureSpeaker: Vida Dujmovic Affiliation: University of Ottawa Location: MC 5501
Abstract: Hadwiger's Conjecture asserts that every Kh-minor-free graph is properly (h-1)-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every Kh-minor-free graph is (h-1)-colourable with monochromatic components of bounded size.