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

用于解决离散问题的连续模型算法及其并行化。

• 批准号: 03680026
• 负责人: IMAI Hiroshi
• 金额: $ 1.28万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1991
• 资助国家: 日本
• 起止时间: 1991 至 1992
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-03680026/
• 关键词: continuous model; linear programming; interior-point method; computational geometry; randomized algorithms; 組合せ最適化; 連続体アルゴリズム; 散離最適化; 丸め法

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.

本研究的目的是考虑离散问题和连续/非线性世界之间的转换，并利用连续模型的良好特性为离散问题开发有效的算法。通过考虑对连续模型的良好变换，在原始离散设置中遇到的组合爆炸有时可能会被克服或至少在某些情况下被削弱。在本研究中，我们主要关注线性规划的内点方法及其在特殊或特殊情况下的应用。网络编程和整数编程等一般情况。关于线性规划，在 20 世纪 80 年代中期，旧的内点方法的变体被认为是最先进的单纯形方法的一种可能的替代方案，特别是对于大规模问题。通过这个研究项目，我们阐明了Iri和Imai提出的线性规划乘法惩罚函数方法的时间复杂度。此外，还提出了将内点方法应用于网络流问题，并论证了其在设计并行算法中的用途。此外，通过详细考虑线性规划的几何性质，线性规划及其相关问题的随机算法被调查。特别是，从确定性和概率性的角度研究了整数规划内点法应用中出现的舍入阶段。还研究了几种舍入过程的并行化。针对点集的一维匹配问题，部分使用了计算几何技术，开发了一种有效的贪婪型算法。

项目成果

H.Imai T.Oomae: "Roundinga Real Vector to an Integral Vector in Integer Programming and Its Porallelization." Proceedings of the JSPS Symposium on Parallel Computing.

H.Imai T.Oomae：“整数规划及其并行化中的实数向量到积分向量的舍入”。

H. Imai: "On the Polynomiality of the Multiplicative Penalty Function Method for Linear Programming and Related Inscribed Ellipsoids." IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. Vol.E74, No.4. 669-671 (1991)

H. Imai：“关于线性规划和相关内接椭球的乘法罚函数方法的多项式”。

H.IMAI: "On the Polynomiality of the Multiplicative Penalty Function Method for Linear Programming and Related Inscribed Ellipsoids." IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,. Vol.E74,No.4. 669-671 (1991)

H.IMAI：“关于线性规划和相关内切椭球体的乘法罚函数方法的多项式”。

T. Akutsu, Y. Aoki, S. Hasegawa, H. Imai and T. Tokuyama: "The Sum of Smaller Endpoint Degree over Edges of Graphs and Its Applications to Geometric Problems." Proceedings of the 3rd Canadian Conference on Computational Geometry, Vancouver. 145-148 (1991)

T. Akutsu、Y. Aoki、S. Hasekawa、H. Imai 和 T. Tokuyama：“图边上较小端点度的总和及其在几何问题中的应用”。

H.IMAI and T.OOMAE: "Rounding a Real Vector to an Integral Vector in Integer Programming and Its Parallelization." Proceedings of the JSPS Symposium on Parallel Computing.

H.IMAI 和 T.OOMAE：“在整数规划及其并行化中将实数向量舍入为整数向量”。