Keynote Speakers

Dr. Naoki Katoh (Kwansei Gakuin University)
Email: naoki@archi.kyoto-u.ac.jp

Title: Optimal sink location problems on dynamic networks
Abstract:
This talk surveys the state of the art of facility location problems in dynamic networks that have been actively studied in recent years. These problems have been motivated by evacuation planning which has become increasingly important in Japan. The evacuation planning problem is formulated by the use of a dynamic network which consists of a graph that models a road network in which a capacity as well as a transit time is associated with each edge, and asks to find a way to evacuate evacuees originally existing at vertices to facilities (evacuation centers) as quickly as possible. The problem can be viewed as a generalization of classical $k$-center and $k$-median problems. We shall show recent results about the difficulty and approximability of a single-facility location for general networks and polynomial time algorithms for $k$-facility location problems in path and tree networks. We also mention the minimax regret version of these problems, and multi-commodity dynamic flow problems.

Dr. Kirk Pruhs (University of Pittsburgh)
Email: kirk@cs.pitt.edu

Title: Green Computing Algorithmics
Abstract:
We are in the midst of a green computing revolution involving the redesign of information technology (IT) hardware and software at all levels of the IT stack with energy efficiency as the first order design constraint. This green computing revolution has spawned a multitude of algorithmic problems involving managing power, energy or temperature as a computational resource. As the physical properties of energy are fundamentally different from the physical properties of time and space, the previous first order design constraints for IT, an algorithmic theory of energy as a computational resource is going to be fundamentally different than the very successful theory of time and space as computational resources at the application layer. The current algorithmic theory of energy as a computational resource predominantly involves properly balancing the conflicting objectives of performance and energy at lower layers of the technology stack. I will explain the reason for this, and illustrate this using some examples from the recent algorithmic literature.