Dr. Naoki Katoh
(Kwansei Gakuin University)
Title: Optimal sink location problems on dynamic networks
Dr. Kirk Pruhs
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
(University of Pittsburgh)
Title: Green Computing Algorithmics
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.