Research on efficient algorithms for discrete structures

我们研究和检查算法，解决问题的离散结构。我们已经获得了新的知识，目前的算法和算法理论的局限性。我们特别研究了并行和分布式算法。我们为设计新的算法打下了基础，并设计和分析了许多新的算法。主要研究结果如下：1.电路划分问题是超大规模集成电路版图设计中的一个重要问题，目前已经提出了许多算法。给定一组模块和一个网表，这里的问题是找到一个最优的划分模块集分为两个，使模块所占用的面积在两侧是可比的，并在两侧之间的互连数量最小化。针对这一问题，我们比较了基于图表示的方法和将模块映射为平面上的点后求解二分问题的方法.对于NP完全问题这样的难题，人们已经开发了许多算法，这些算法被称为平均运行速度快。通常，他们的表现已经估计数学分析，但特别是对于实际的目的，它也应该是重要的，以估计他们实际运行的算法。我们讨论了如何满足性问题的实例，这是用来衡量算法的性能，应该产生。我们，反过来，展示了几个实例生成算法，满足所考虑的要求。

We studied and examined algorithms which solve problems for discrete structures. We have obtained new knowledge about limitations of current algorithms and algorithm theory. We especially studied parallel and distributed algorithms. We have constructed a base for designing new algorithms, and then, designed and analyzed many new algorithms. The main results are as follows.1. One of the most important problems in VLSI layout design is a circuit partitioning problem, for which a number of algorithms have been presented. Given a set of modules together with a net list, the problem here is to find an optimal partition of the module set into two so that the areas occupied by modules are comparable in the two sides and the number of interconnections between two sides is minimized. For this problem we compared the method based on graph representation with the one of solving the bipartition problem after mapping modules into points in the plane.2. For intractable problems such as NP-complete problems, a lot of algorithms, which are claimed to run fast on average, have been developed. Usually their performances have been estimated by methematical analysis but, especially for practical purposes, it should be also important to estimate them by actually running the algorithms. We discussed how instances of the satisfiability problem, which are to be used to scale the performance of the algorithms, should be generated. We, in turn, showed several instance-generation algorithms that meet the requirements considered.