Research on Algorithms for Discrete Optimization Problems with Dynamic and On-Line Environments.

点击翻译按钮获取中文摘要

The aim of this research is to develop efficient algorithms for discrete optimization problems under dynamic and on-line environments. Many practical problems have dynamic and on-line natures, and algorithms should be newly designed to handle dynamic and on-line factors.First, we consider the dynamic shortest path problem where the distances of edges vary dynamically. This problem arises in real-time route navigation system where traffic jams makes the edge costs higher. We have developed A^*-based algorithms which make clever use of past solutions. Other techniques such as bidirectional search are also investigated. Also, to cope with future dynamic situations, a new algorithm to compute multiple candidates for route navigation in the given static environment is developed.We formulate probelems of sharing information in distributed systems as an on-line model, and developed efficient on-line algorithms. The on-line nature is inherent in the distributed system, and we mainly consider page migration and replication probelms. To evaluate the on-line algorithms the so-called competitive ratio is used. Efficient algorithms in term of this ratio have been derived. Randomized techniques are demonstrated to be powerful for on-line problems.Dynamic computational geometry is also investigated, especially the Voronoi diagram for dynamically moving points. The combinatorial complexity of dynamic Voronoi diagram is shown, together with its efficient construction algorithm. This is further applied to geometric clustering problem which have both discrete and continuous aspects. Randomized algorithms are developed by making use of these two aspects.We have thus clarified fundamental structures of dynamic and on-line problems, and developed new paradigms to solve this new type of problems.