Evacuation Problems on Cycle Networks

Speaker:        Professor Tiko Kameda
                Professor Emeritus of Computing Science
                Simon Fraser University

Title:          "Evacuation Problems on Cycle Networks"

Date:           Friday, 16 November 2018

Time:           4:00pm - 5:00pm

Venue:          Room 5583 (via lifts 29/30), HKUST

Abstract:

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. 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. We
assume that congestion can develop only at vertices, not on edges.

The 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. Low-degree polynomial time algorithms are known
for path and tree networks.

In this talk, we first discuss the k-sink problem on cycle networks. 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 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. We present an algorithm for finding a
minmax-regret 1-sink on cycle networks.


*******************
Biography:

Tiko Kameda is Professor Emeritus of Computing Science at Simon Fraser
University. Prior to his retirement in 2004, he was Professor at SFU since
1980, and Assistant and Associate Professor in the Department of
Electrical Engineering at the University of Waterloo since 1967. He
received his Ph.D. in Electrical Engineering from Princeton University in
1968, M.S. in Electronics Engineering from the University of Tokyo in
1963, and B.S. in Electrical Engineering from the University of Tokyo in
1961. He was the Director of the Laboratory for Computer and
Communications Research at SFU from 1982 to 1997. He had a number of
visiting appointments with Kyoto University and Kyushu University in
Japan, and University of Karlsruhe, University of Frankfurt, University of
Erlangen-Nuernberg, University of Braunschweig, and Gesellschaft fuer
Mathematik und Datenverarbeitung in Germany. His current research interest
lies mainly in the design and analysis of efficient algorithms for
facility location problems, in particular evacuation problems in different
families of networks. In the past, he has worked in the areas of automata
theory, system diagnosis, graph problems, combinatorial algorithms, coding
theory, database theory, system diagnosis, video-on-demand schemes,
distributed computing, etc. He has written three books and published about
150 journal and conference papers.