Algorithms on continuous models for solving discrete problems and their parallelization.

这项研究的目的是考虑离散问题与连续/非线性世界之间的转换，并利用连续模型的良好性质开发出求解离散问题的有效算法。本文主要研究线性规划的内点法及其在网络规划、整数规划等特殊或一般情况下的应用。关于线性规划，在20世纪80年代中期，S认为旧的内点法的变体被认为是最先进的单纯形法的一种可能的替代方案，特别是对于大规模问题。通过这个研究项目，我们澄清了IRI和Imai提出的线性规划的乘性罚函数方法的时间复杂性。在此基础上，提出了将内点法应用于网络流问题，并说明了内点法在并行算法设计中的应用；同时，通过详细考虑线性规划的几何性质，研究了线性规划的随机化算法及其相关问题。特别是，从确定性和概率的角度研究了整数规划内点法应用中的舍入阶段。研究了几种四舍五入算法的并行化问题，利用计算几何技术，提出了一种高效的贪婪算法，用于求解点集的一维匹配问题。

The aim of this research is to consider transformations between discrete problems and continuous/nonlinear worlds, and to develop efficient algorithms for discrete problems using the good properties of continuous models. By considering good transformations to continuous models, combinatorial explosion encountered in the original discrete settings might be sometimes overcome or at least weakened in some cases.In this research, we mainly focus on the interior-point method for linear programming and its application to special or generalized cases such as network programming and integer programming. Concerning linear programming, in mid 1980's, variants of the old interior-point method was considered as a possible alternative, especially for large-scale problems, to the state-of-the-art simplex method. Through this research project, we have clarified the time complexity of the multiplicative penalty function method for linear programming which was proposed by Iri and Imai. Furthermore, applying the interior-point method to network flow problems has been proposed, and its use in designing parallel algorithms has been demonstrated.Also, by considering the geometric properties of linear programming in detail, randomized algorithms for linear programming and its related problems have been investigated. Especially, the rounding stage arising in the application of the interior-point method for integer programming has been studied from deterministic and probabilistic viewpoints. Parallelization of several rounding procedures has been also investigated.An efficient greedy-type algorithm has been developed for the one-dimensional matching problems for point sets, partially using the technique of computational geometry.