Fast Exact Algorithms for Interdiction Problems - Coffee Talk

Explore fast exact algorithms for interdiction problems in this 48-minute DS4DM Coffee Talk presented by Ricardo Fukasawa from the University of Waterloo, Canada. Delve into the concept of interdiction problems as a form of Stackelberg game involving two decision-makers: a leader and a follower. Examine how these zero-sum games can be significantly more challenging than their classical counterparts, both in terms of complexity and algorithm performance. Focus on two variants of the problem where the leader must satisfy a knapsack constraint, with the follower solving either a knapsack or minimum spanning tree problem. Learn about the branch-and-bound algorithms with carefully devised bounding schemes that significantly improve the limits of exact algorithms for these problems. Gain insights into the potential for further research in this area, based on joint work with Noah Weninger.

Fast exact algorithms for some interdiction problems, Ricardo Fukasawa