Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2014-15 > A graph patrol problem with random attack times
How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE


Enquiries: dom.events@lse.ac.uk 


Follow us online



A graph patrol problem with random attack times

Wednesday 11 March 2015
Kevin Glazebrook

4pm - 5pm, OLD 1.27, Old Building, Houghton Street 


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.

Kevin Glazebrook