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

本研究的目的是发展有效的算法，在动态和在线环境下的离散优化问题。许多实际问题都具有动态性和在线性，需要设计新的算法来处理动态性和在线性因素。首先，我们考虑了边的距离动态变化的动态最短路问题。这个问题出现在实时路线导航系统中，其中交通堵塞使得边缘成本更高。我们开发了基于A^* 的算法，巧妙地利用了过去的解决方案。其他技术，如双向搜索也进行了研究。此外，为了科普未来的动态情况下，一个新的算法来计算多个候选路径导航在给定的静态environment.We制定问题的共享信息在分布式系统作为一个在线模型，并开发了有效的在线算法。分布式系统的在线性是分布式系统固有的特性，本文主要考虑了页面迁移和复制问题。为了评估在线算法，使用所谓的竞争比。有效的算法在这个比例方面已经得到。随机化技术被证明是强大的在线问题。动态计算几何也进行了研究，特别是动态移动点的Voronoi图。给出了动态Voronoi图的组合复杂性及其有效的构造算法。这进一步适用于几何聚类问题，同时具有离散和连续的方面。利用这两个方面发展了随机化算法，从而阐明了动态问题和在线问题的基本结构，并发展了解决这类新问题的新范式。

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.