Title: Shortest Path Interdiction and Total Reward Games
Speaker: Endre Boros, RUTCOR Director, Rutgers University
Date: Monday, September 24, 2012 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Interdiction problems arise when one would like to manipulate a system in order to change some of its extreme characteristics. Typically such manipulations are costly, and limited resources lead to optimization problems. A malicious example is shortest path interdiction, in which an enemy force can destroy some of the links of a network (transportation, communication, gas, oil, etc.) in order to diminish its usefulness, e.g., increase the shortest path between given pairs of nodes as much as possible. We give a brief survey of this problem and its variants, show a natural game theoretic interpretation, and analyze the resulting new family of stochastic games.
DIMACS/CCICADA Interdisciplinary Series, Complete Fall Calendar 2012