Date:  11:2012:00, Thursday, March 26, 2009 
Venue:  FIT Building 1315, Tsinghua University 
Title:  Network interdiction 
Speaker:  Daniel Andersson 
Biography: 
Daniel Andersson got his master degree in science of computer science in Uppsala University in Sweden in 2006. Now he is a PhD scholar in Department of computer science in Aarhus University in Denmark. He won the second place in the 2008 ACM Nordic Collegiate Programming Contest. 
Abstract: 
Network interdiction is a type of zerosum game where one player (the interdictor) wants to decrease the usefulness of a network to the other (the user). This is a classic problem type in operations research, but solution methods typically resort to mixed integer programming.
Khachiyan et al. (2008) consider network interdiction where the user wants to build a minimumweight path and the interdictor can remove edges subject to vertexlocal budgets. They show that optimal strategies can be efficiently computed with a modified Dijkstra's algorithm.
We extend the model of Khachiyan et al. in two directions, by allowing partial interdiction of edges and various ways to define the weight of a path, and we show that efficient algorithms still exist.
