Wednesday 11 March 2015
4pm - 5pm, OLD 1.27, Old Building, Houghton Street
Abstract
A patroller traverses a graph to detect and then thwart potential attacks at nodes. In deciding how to patrol, the patroller needs to take account of many things: the structure of the graph, the possibly different attack time distributions at distinct nodes, the different costs which may be incurred depending on where an attack takes place. Simple, natural ways of patrolling (like repeatedly walking up and down a line graph) may perform poorly. Both random and strategic attackers are considered in the work. We use Lagrangian relaxation to develop index-based heuristics which are easy to compute and which typically achieve within 1% of (cost) optimality.
Based on joint work with Kyle Y Lin, Michael Atkinson and Timothy Chung.