Darboux transformations for factorable Laplace operators

Factorable Laplace operators of the form L = ? _x ? _y + a? _x + b? _y + c, where the coefficients a, b, c are not necessarily constants, are considered. For these operators, the Darboux transformations \(L\xrightarrow{M}L_1\) , M ∈ K[? _x ], defined by the intertwining relation NL = L ₁ M are considered. It is shown that only the following cases are possible: either (1) M ∩ ker? _x + b = {0} and L ₁ is also factorable or (2) M ∩ ker? _x + b contains a nonzero element. We prove that, in both cases, the Darboux transformation can be represented as a product of first-order Darboux transformations. For case (2), the proof is based on the fact that the Darboux transformation of operator L can be reduced to Darboux transformations of first-order operators.     

A new algorithm for constructing approximate transformations fornonlinear systems

An algorithm is provided for constructing an approximating transformation for a feedback linearizable system, and for a system that is not feedback linearizable. Instead of approximating the given nonlinear system, the authors approximate the transformation in a proper sense. They assume that the lead variables of a transformation have a certain form with unknown parameters, substitute these variables into the required equations, and determine the unknown parameters through linear algebraic equations. There is a tremendous savings in terms of number of equations and unknowns, and it is sometimes possible to find exact (or best possible) transformations in a surprisingly small number of steps     

An algorithm for constructing toric compactifications

The paper puts forward a computer algebra algorithm to calculate parameters of toric compactification of ? ⁿ in which a given smooth toric variety can be embedded as a “skeleton of infinity.” Such a compactification of an affine space extends the well-known decomposition ? _n = ? ⁿ ? ? _n?1 ^∞ . The implementation of the algorithm in the computer algebra system Maple is described.     

An algorithm for constructing a university faculty timetable

A method for constructing a University faculty timetable is described. The method is a modification of Almond's method (Almond M. Comput J. 12, 215–217, 1969) which did not consider the undesired times for giving lectures, availability of lecturers, and their requests. Also, Almond's recording method can put the program in an unclosed loop because the course may be inserted in a period of a fixed course. These points are taken into consideration in the author's algorithm.     

一种基于熵的连续属性离散化算法

连续属性离散化的关键在于合理确定离散化划分点的个数和位置。为了提高无监督离散化的效率,给出一种基于熵的连续属性离散化方法。该方法利用连续属性的信息量 (熵 )的特性,通过对连续属性变量的自身划分,最小化信息熵的减少和区间数,并寻求熵的损失与适度的区间数之间的最佳平衡,以便得到优化的离散值。实验表明该算法是行之有效的。     

An efficient distributed algorithm for constructing small dominating sets

The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network applications, where it is important to locate a small number of centers in the network such that every node is nearby at least one center. Finding a dominating set of minimum size is NP-complete, and the best known approximation is logarithmic in the maximum degree of the graph and is provided by the same simple greedy approach that gives the well-known logarithmic approximation result for the closely related set cover problem. We describe and analyze new randomized distributed algorithms for the dominating set problem that run in polylogarithmic time, independent of the diameter of the network, and that return a dominating set of size within a logarithmic factor from optimal, with high probability. In particular, our best algorithm runs in rounds with high probability, where n is the number of nodes, is one plus the maximum degree of any node, and each round involves a constant number of message exchanges among any two neighbors; the size of the dominating set obtained is within of the optimal in expectation and within of the optimal with high probability. We also describe generalizations to the weighted case and the case of multiple covering requirements. Received: January 2002 / Accepted: August 2002 RID="*" ID="*" Supported by NSF CAREER award NSF CCR-9983901 RID="*" ID="*" Supported by NSF CAREER award NSF CCR-9983901     

An algorithm for computing generalized Euler's transformations of series

An algorithm for computing generalized Euler's transformations of series is established. In comparison with known algorithm, the number of the arithmetic operations results to be slightly reduced. Numerical comparisons with the ε-algorithm are displayed.     

An efficient algorithm for constructing a cryptosystem which is harder to break than two other cryptosystems

Suppose that two organizations with their own separate cryptosystems are put into a context in which they must communicate. An example might be two businesses—accustomed to using different commercial cryptosystems—which have recently merged. Each might mistrust the security of the other's cryptosystem. But neither could quarrel with a process which took their two cryptosystems and yielded a third cryptosystem which was demonstrably at least as strong as either of the original two. This paper constructs a practical working model of such a “least upper bound” of two cryptosystems.     

An algorithm for constructing convexity and monotonicity-preserving splines in tension

In this paper we consider the problem of constructing an interpolatory spline in tension that matches the convexity and monotonicity properties of the data. In this connection, an algorithm is presented relying on the asymptotic properties of the splines in tension and making use of the generalized Newton-Raphson methods developed by Ben-Israel. The numerical performance of the proposed algorithm is tested and discussed for several data sets.     

An algorithm for capturing variables dependences in test suites

The use of dynamic dependence analysis spans several areas of software research including software testing, debugging, fault localization, and security. Many of the techniques devised in these areas require the execution of large test suites in order to generate profiles that capture the dependences that occurred between given types of program elements. When the aim is to capture direct and indirect dependences between finely granular elements, such as statements and variables, this process becomes highly costly due to: (1) the large number of elements, and (2) the transitive nature of the indirect dependence relationship.The focus of this paper is on computing dynamic dependences between variables, i.e., dynamic information flow analysis or DIFA. First, because the problem of tracking dependences between statements, i.e., dynamic slicing, has already been addressed by numerous researchers. Second, because DIFA is a more difficult problem given that the number of variables in a program is unbounded. We present an algorithm that, in the context of test suite execution, leverages the already computed dependences to efficiently compute subsequent dependences within the same or later test runs. To evaluate our proposed algorithm, we conducted an empirical comparative study that contrasted it, with respect to efficiency, to three other algorithms: (1) a naïve basic algorithm, (2) a memoization based algorithm that does not leverage computed dependences from previous test runs, and (3) an algorithm that uses reduced ordered binary decision diagrams (roBDDs) to maintain and manage dependences. The results indicated that our new DIFA algorithm performed considerably better in terms of both runtime and memory consumption.     

概念特化的概念格更新构造算法

概念格是形式概念分析中的核心数据结构,概念格应用的瓶颈之一是其构造效率. 针对形式背景的某个属性分解为多个新属性得到更加特化的概念,给出了一种基于概念特化的渐进式更新构造算法. 该算法利用分解后的新属性及其相应的形式背景,构造出的概念格与原概念格的某个子概念格作比较,来更新构造概念格,从而减少了比较次数,提高了更新构造的效率. 以天体光谱数据作为形式背景,实验验证了该算法的正确性和有效性.     

An efficient algorithm for constructing delay bounded minimum cost multicast trees

Multimedia applications are usually resource intensive, have stringent quality of service requirements, and in many cases involve large groups of participants. Multicasting is poised to play an important role in future deployment of these applications. This paper focuses on developing delay-bounded, minimum-cost multicast trees, linking a source to a set of multicast destination nodes. The approach taken in this paper is efficient, flexible and unique in the sense that it cleverly limits its computation only to paths that originate at multicast nodes, thereby avoiding computing paths that exclusively link non-multicast nodes. The simulation results show that the multicast trees produced by the proposed heuristic are of lower cost than those produced by other well-known heuristics, including those which use an expensive k-shortest-paths procedure to minimize the cost of the multicast tree. Furthermore, the results show that, in comparison to other heuristics, the proposed scheme results in a significant reduction in the computation time required to build the multicast tree.     

An adaptive ant colony optimization algorithm for constructing cognitive diagnosis tests

A critical issue in the applications of cognitive diagnosis models (CDMs) is how to construct a feasible test that achieves the optimal statistical performance for a given purpose. As it is hard to mathematically formulate the statistical performance of a CDM test based on the items used, exact algorithms are inapplicable to the problem. Existing test construction heuristics, however, suffer from either limited applicability or slow convergence. In order to efficiently approximate the optimal CDM test for different construction purposes, this paper proposes a novel test construction method based on ant colony optimization (ACO-TC). This method guides the test construction procedure with pheromone that represents previous construction experience and heuristic information that combines different item discrimination indices. Each test constructed is evaluated through simulation to ensure convergence towards the actual optimum. To further improve the search efficiency, an adaptation strategy is developed, which adjusts the design of heuristic information automatically according to the problem instance and the search stage. The effectiveness and efficiency of the proposed method is validated through a series of experiments with different conditions. Results show that compared with traditional test construction methods of CDMs, the proposed ACO-TC method can find a test with better statistical performance at a faster speed.     

不同蕴涵算子下三I方法的解

以R_M、R_Z、R₀三个蕴涵算子为基础,研究了11种形式的三I算法的解,并在此基础上给出了这11种解的同一形式：B*（y）=SUP{A*（x）∧φ（x,y）},其中φ：X×Y→[0,1]表示某一函数,而且φ（x,y）与E_Y的选取依赖蕴涵算子R_i的选取。     

An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS-15361.     

An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.     

An algorithm for constructing single machine schedules based on ant colony approach

A mathematical statement of the problem of building a schedule of data exchange over a channel with centralized control is presented. This problem arises in the design of real-time management information systems (MISs). Various approaches to the design of ant colony algorithms are analyzed, and experimental comparison of the proposed algorithm with greedy algorithms is performed.     

An algorithm for constructing a minimal partial realization in the multivariable case

It is known that the Berlekamp-Massey algorithm from information theory can be used to compute scalar minimal partial realizations. Recently, it has been interpreted in terms of exact modeling of behaviors. In this paper, we extend these results to the multivariable case. We put the behavioral theory of exact modeling to work in deriving an extension of the Berlekamp-Massey algorithm for computing multivariable minimal partial realizations.     

An algorithm for constructing project network diagrams on an ordinary line printer

An algorithm for generating activity-on-arrow network diagrams is presented that does not need a graph plotter for its application, and can print networks of practical size within reasonable computer time. Computational experience is reported.