*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: Dynamic Network Interdiction: Bounds and Optimal Algorithms
ABSTRACT:
This talk discusses some collaborative work between the presenter and Dr. Jorge Sefair, an assistant professor at Arizona State University. We study two dynamic network games between an attacker and a user. In the first, the user seeks a shortest path between a pair of nodes in a directed network, and the attacker seeks to interdict a subset of arcs to maximize the user’s shortest-path cost. In contrast to most previous studies, the attacker can interdict arcs any time the user reaches a node in the network, and the user can respond by dynamically altering its chosen path. We assume that the attacker can interdict a limited number of arcs, and that an interdicted arc can still be traversed by the user at an increased cost. The challenge is therefore to find an optimal path, coupled with the attacker’s optimal interdiction strategy. We propose an exact exponential-state dynamic-programming algorithm for this problem, along with algorithms that produce lower and upper bounds on the optimal objective function value. A second problem examines a similar problem in dynamic assignment problems. Interestingly, while the shortest-path variant is polynomially solvable when the interdictor can attack only one arc, the assignment variation becomes strongly NP-hard when the interdictor has a single assignment that can be interdicted.
Bio:
Dr. J. Cole Smith is Professor and Chair of the Industrial Engineering department at Clemson University. His research has been supported by the NSF, DARPA, AFOSR, DTRA, and the ONR, and he has spent one summer as a Distinguished Visiting Professor in the National Security Agency’s summer program in operations research technology. His research regards mathematical optimization models and algorithms, especially those arising in combinatorial optimization. Dr. Smith has had the pleasure of collaborating with colleagues across many different disciplines, including Mathematics, Ecology, Psychology, Computer Science, and Biomedical Engineering. His awards include the Young Investigator Award from the ONR, the Hamid K. Elden Outstanding Young Industrial Engineer in Education award, the Operations Research Division Teaching Award, the 2014 Glover-Klingman prize for best paper in Networks, and the best paper award from IIE Transactions in 2007.
