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

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

A graph patrol problem with random attack times

Wednesday 11 March 2015
Kevin Glazebrook

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.

Share:Facebook|Twitter|LinkedIn|
Kevin Glazebrook