Research on efficient algorithms for discrete structures

我们研究和检验了解决离散结构问题的算法。我们对现有算法和算法理论的局限性有了新的认识。我们特别研究了并行和分布式算法。为设计新的算法奠定了基础，并设计和分析了许多新的算法。主要研究结果如下：1.研究结果。电路划分问题是VLSI版图设计中最重要的问题之一，已有许多算法被提出。在给定一组模块和一个网表的情况下，这里的问题是找出模块集的最优分割成两个模块，使得模块占据的面积在两侧是可比较的，并且使两侧之间的互连数目最小。针对这一问题，我们比较了基于图表示的方法和将模映射到平面上的点来解决二分问题的方法。对于像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.