Improved approximation algorithms for MAXk-CUT and MAX BISECTION

Polynomial-time approximation algorithms with nontrivial performance guarantees are presented for the problems of (a) partitioning the vertices of a weighted graph intok blocks so as to maximize the weight of crossing edges, and (b) partitioning the vertices of a weighted graph into two blocks of equal cardinality, again so as to maximize the weight of crossing edges. The approach, pioneered by Goemans and Williamson, is via a semidefinite programming relaxation. The first author was supported in part by NSF Grant CCR-9225008. The work described here was undertaken while the second author was visiting Carnegie Mellon University; at that time he was a Nuffield Science Research Fellow, and was supported in part by Grant GR/F 90363 of the UK Science and Engineering Research Council, and Esprit Working Group 7097 “RAND”.     

Factored Edge-Valued Binary Decision Diagrams

Factored Edge-Valued Binary Decision Diagrams form an extension to Edge-Valued Binary Decision Diagrams. By associating both an additive and a multiplicative weight with the edges, FEVBDDs can be used to represent a wider range of functions concisely. As a result, the computational complexity for certain operations can be significantly reduced compared to EVBDDs. Additionally, the introduction of multiplicative edge weights allows us to directly represent the so-called complement edges which are used in OBDDs, thus providing a one to one mapping of all OBDDs to FEVBDDs. Applications such as integer linear programming and logic verification that have been proposed for EVBDDs also benefit from the extension. We also present a complete matrix package based on FEVBDDs and apply the package to the problem of solving the Chapman-Kolmogorov equations.     

BSP模型及其并行程序设计

当前并行计算领域的研究重点和热眯是研究“通用”并行计算的适用范围，而其中心议题是既具有可扩展并行性又同时具有体系结构独立必的可移植软件开发方法和工具的研究。解决体系结构独立的途径是通过引入的一个过渡模型使得软件和硬件得以较好的分离。ＢＳＰ（Ｂｕｌｋ Ｓｙｎｃｈｕｏｎｏｕｓ Ｐａｒａｌｌｅｌ）模型正是这样一个理论模型，它不但可提供既具有可扩展的并行性又独立于体系结构的并行软件开发方法，而且可为并行和     

Recursive parser optimization by rewriting context-free grammars

The analysis of programming languages is a fundamental activity in the process of comprehending, maintaining, documenting and reengineering old software. However, the analysis may sometimes be inefficient because of the parsing methodology adopted. Prolog parsers, for instance, have two main drawbacks: the time spent on extracting information as a result of the backtracking mechanism, and the large memory occupation involved. This paper presents an algorithm that optimizes a top-down parser by imposing a set of rules on the grammar to be analyzed. A methodology is then defined for rewritting a context-free grammar (LL(n) n > = 1), and a tool that can achieve this is illustrated. This tool, called FACTOTUM, has been implemented in LPA Prolog, and works on a PC (IBM-MSDOS) through the Windows medium. FACTOTUM is composed of nearly 250 productions, and is an important part of another reverse engineering tool called RE_Tool (Giannone and Maresca, 1995) which can analyze codes in a multilanguage environment. RE_Tool has been implemented in the software engineering laboratories of DIS at the University of Naples Federico II, where it is currently under experimentation.     

科学计算可视化的研究现状和发展趋势

科学计算可视化作为８０年代后期在计算机图形学的基础上发展起来的一种全新的计算风格，日益受到人们的重视，并在航空航天、船舶、建筑等许多领域得到越来越广泛的应用。本文阐述了ＶＩＳＣ的发展历程，首先指出了ＶＩＳＣ的研究领域得到越来越 广泛的应用。     

求解线性规划问题的一类新的连续化方法

针对一类线性规划问题的解存在的新等价性条件，给出了大范围收敛的连续化方法及证明了收敛性的结论。     

电力系统无功功率的模糊优化控制

本文应用模糊集合理论来实现电力系统的无功功率最优化控制，通过求解约束条件和目标函数的模糊集合的交集，得出有功功率损耗最了优运行状态；与非模糊方法的结果进行比较，从而显示它的损耗更小，收敛更快的优点。     

检修计划新模型与算法的研究

本文在研究检修计划问题的内在特点基础上，建立了基于整数规划的检修计划优化模型和算法。记叙虎法直接根据约束系数矩阵Ａ中每台机组所对应元素的最小和最大值来分别消去不可行分支解和待校验约束，从而显著缩小了问题求搜索空间。本文最后给出了算例。     

一种求解大规模稀疏二次规划的迭代法

运用部分松驰乘子法将一般二次规划化成一系列带简单约束的严格凸二次规划，然后利用广义共轭梯度法来求解这些特殊的二次规划，同时得到了原问题的对偶解，并给出了算法的有关收敛性结果和数值结果     

几何规划的一种有效算法

在对偶理论作用下约束正定式几何规划转变为线性等式约束下的非线性规划。利用了近年来即约梯度法的最新研究成果以及几何规划目标和约束函数的特点，为几何规划构造了一种有效的间接算法。