The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:

A Game for Optimizing Randomized Patrols on a Network


Speaker: Dr. Katerina Papadaki
Affiliation: London School of Economics, UK
Category: Colloquium
Location: Room 148, Faculty of Pure and Applied Sciences (FST-01), 1 University Avenue, 2109 Nicosia, Cyprus (directions)
Date: Monday, December 21, 2009
Time: 11:00-12:00 EET
Host: Andreas Pitsillides (andreas.pitsillides AT

This paper describes a class of patrolling games on graphs, motivated by the problem of patrolling a network vulnerable to viral infection or a facility (for example in order to defend an art gallery against theft of a painting, or an airport against terrorist attack). The network/facility can be thought of as a graph Q of interconnected nodes (e.g. rooms, terminals) and the Attacker can choose to attack any node of Q within a given time T. He requires m consecutive periods there, uninterrupted by the Patroller, to commit his nefarious act (and win). The Patroller can follow any path on the graph. Thus the patrolling game is a win-lose game, where the Value is the probability that the Patroller successfully intercepts an attack, given best play on both sides. We determine analytically optimal (minimax) patrolling strategies for various classes of graphs, and present numerical results for some intractable cases. Joint work with Steve Alpern and Alec Morton

Short Bio:
Katerina Papadaki is a tenured Lecturer in the Operational Research Group, Department of Management at the London School of Economics. She received her PhD from Princeton University in 2002, from the Department of Operational Research and Financial Engineering, her MSc in Operational Research from the London School of Economics in 1996, and her BA in Pure Mathematics and Statistics from the University of California at Berkeley in 1994. A major component of her research has been in developing algorithms to solve stochastic multidimensional dynamic programs that arise in dynamic resource allocation problems with applications involving physical resources (transportation networks), and radio resource allocation (wireless communication networks). Subsequently, using discrete optimization techniques she has developed algorithms for scheduling and routing problems in cellular wireless networks. Amongst others, she has worked on robust optimization techniques for scheduling, facility location routing problems, and network optimization on vehicular communications and intelligent transportation systems. Recently, her research attention has been on game theoretic problems. These include fair allocation of resources in telecommunication networks using cooperative game theory, inspection games with applications in inspections of NHS hospitals, and network patrolling games with applications in network security. She is associate editor of Optimization Letters and a member of INFORMS and IEEE.

  Mailing List:

Sponsor: The CS Colloquium Series is supported by a generous donation from Microsoft