Title:Survey on Graph Evacuation Problems
Date: November 13, 2018 (Tuesday)
Time: 10:00 am - 11:00 am
Venue: Room 121, 1/F, Ho Sin-hang Engineering Building, The Chinese University of Hong Kong, Shatin, N.T.
Speaker: Prof. Tiko Kameda
Professor Emeritus
School of Computing Science at Simon Fraser University


Due to many recent disasters such as typhoons, earthquakes, volcanic eruptions, and nuclear accidents, evacuation planning is getting increasing attention. We model evacuation by dynamic flow in networks, where a given number of evacuees is initially located at each vertex. Each edge has a length and a capacity, which is the number of evacuees who can enter it per unit time. We assume the transit time across an edge is proportional to its length. Such a graph can model airplane aisles, rooms and corridors in a building, houses and city streets, cities and inter-city highways, etc. Starting at time 0, all evacuees move towards sinks.

The completion time k-sink problem is to find k sinks in a network such that the evacuation completion time to sinks is minimized. It is somewhat similar to the k-center problem, but here congestion can develop due to the limited edge capacities. In the aggregate time k-sink problem, the objective function is the sum of the evacuation time of every evacuee. Low-degree polynomial time algorithms are known for path, tree and cycle networks, which we will review in this talk.

In the real world, it is likely that the exact values (such as the number of evacuees at the vertices) are unknown. The concept of "regret" was introduced by Kouvelis and Yu in 1997, to model the situations where optimization is required when the exact values are unknown, but are given by upper and lower bounds. A particular instance of the set of evacuee numbers, one for each vertex, is called a "scenario”. The objective of the minmax-regret problem is to find a solution which is as good as any other solution in the worst case, where the actual scenario is the most unfavorable. It can be defined for both completion time and aggregate time objective functions. We review results on the minmax-regret problem for path, tree and cycle networks.



Prof. Tiko Kameda is now a Professor Emeritus of School of Computing Science at Simon Fraser University. His current research interest lies mainly in the design and analysis of efficient algorithms for facility location problems, in particular evacuation problems in different networks. In the past, he has worked in the areas of automata theory, system diagnosis, graph problems, combina-torial algorithms, coding theory, database theory, system diagnosis, video-on-demand schemes, distributed computing, etc.


Enquiries: Ms. Crystal Tam at tel. 3943 8439

For more information, please refer to http://www.cse.cuhk.edu.hk/en/events