CS Colloquium Series @ UCY
Department of Computer Science - University of Cyprus
The Department of Computer Science at the University of Cyprus holds research colloquiums and social hours approximately once weekly. All university students, faculty, and staff are invited to attend. Notifications about new and upcoming events are automatically disseminated to a variety of institutional lists.
If you don't receive these notifications, but want to get informed about upcoming colloquium announcements, you can do the following:
List
RSS
Directions
Colloquium Coordinator: Demetris Zeinalipour
Colloquium: A Game for Optimizing Randomized Patrols on a Network, Dr. Katerina Papadaki (London School of Economics, UK), Monday, December 21, 2009, 11:00-12:00 EET.
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 |
Abstract:
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.
Sponsor: The CS Colloquium Series is supported by a generous donation from  |