Resolution principle for the minimum covering problem of a 0–1 matrix

Conclusion Our experiments establish sufficient efficiency of the g.r.p. for MCP (WMCP), and in many cases show it to be superior by running time to the branch-and-bound method for this problem. The analytical bounds given above point to stable behavior of the g.r.p. Note that in the theoretical arguments of the previous section we have assumed that in the generated resolvent column at least one 1 is distributed with probability of order 1/k among the rows in a covering withk or fewer rows. Of the two rows α, β from the sought covering and such that α contains a greater number of 1s than β, α obviously has a higher probability of getting a 1 in the resolvent column than β. However, each time that the “greedy” algorithm prefers row α over row β (includes α in the covering and does not include β), a cutting column is constructed by Theorem 2 in which α is guaranteed to contain 0. Thus, the more times row α is selected without row β, the higher the number of additional 1s accumulated in row β. This suggests that the number of 1s in rows α and β tends to equalize. This argument can be extended to any pair of rows in the sought covering. The argument presented in this paper is thus valid on average. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 135–146, January–February, 1996.     

Convergence of bpsd method for T (q,r) matrix

In this paper, we obtain a necessary and sufficient condition, when the coefficient matrix A of the equation Ax = f considered is a T(l, 1) matrix, a sufficient condition, when A is a T(l, 2) or T(2, 1) matrix for the convergence of BPSD method. We also obtain the optimum parameters and the optimum rate of convergence of BPSD method, when A is T(l, 1) matrix and a necessary and sufficient condition, when A is positive definite and we point out that the necessary and sufficient condition in [1] and [9] is only sufficient.     

Optimal (N,T)-policy for M/G/1 system with cost structures

In this paper, the optimal (N,T)-policy for M/G/1 system with cost structure is studied. The system operates only intermittently. It is shut down when no customers are present. A fixed set-up cost of K>0 is incurred each time the system is reopened. Also, a holding cost of h>0 per unit time is incurred for each customer present. The (N,T)-policy studied for this system is as follows: the system reactivates as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T (see A.S. Alfa, I. Frigui, Eur. J. Oper. Res. 88 (1996) 599-613; Y.N. Doganata, in: E. Arikan (Ed.), Communication, Control, and Signal Processing, 1990, pp. 1663–1669). Later on, as a comparison, the start of the timer count is relaxed as follows: the system reactivates as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. For both cases, the explicit optimal policy (N^*,T^*) for minimizing the long-run average cost per unit time are obtained. As extreme cases, we include the simple optimal policies for N-and T-polices. Several counter-intuitive results are obtained about the optimal T-policies for both types of models.     

A unified theory for optimal feedforward torque control of anisotropic synchronous machines

A unified theory for optimal feedforward torque control of anisotropic synchronous machines with non-negligible stator resistance and mutual inductance is presented which allows to analytically compute (1) the optimal direct and quadrature reference currents for all operating strategies, such as maximum torque per current (MTPC), maximum current, field weakening, maximum torque per voltage (MTPV) or maximum torque per flux (MTPF), and (2) the transition points indicating when to switch between the operating strategies due to speed, voltage or current constraints. The analytical solutions allow for an (almost) instantaneous selection and computation of actual operation strategy and corresponding reference currents. Numerical methods (approximating these solutions only) are no longer required. The unified theory is based on one simple idea: all optimisation problems, their respective constraints and the computation of the intersection point(s) of voltage ellipse, current circle or torque, MTPC, MTPV, MTPF hyperbolas are reformulated implicitly as quadrics which allows to invoke the Lagrangian formalism and to find the roots of fourth-order polynomials analytically. The proposed theory is suitable for any anisotropic synchronous machine. Implementation and measurement results illustrate effectiveness and applicability of the theoretical findings in real world.     

Near-Optimal Reinforcement Learning in Polynomial Time

We present new algorithms for reinforcement learning and prove that they have polynomial bounds on the resources required to achieve near-optimal return in general Markov decision processes. After observing that the number of actions required to approach the optimal return is lower bounded by the mixing time T of the optimal policy (in the undiscounted case) or by the horizon time T (in the discounted case), we then give algorithms requiring a number of actions and total computation time that are only polynomial in T and the number of states and actions, for both the undiscounted and discounted cases. An interesting aspect of our algorithms is their explicit handling of the Exploration-Exploitation trade-off.     

Hardware accelerator for solving 0–1 knapsack problems using binary harmony search

The 0–1 knapsack problem (KP) is a well-known intractable optimization problem with wide range of applications. Harmony Search (HS) is one of the most popular metaheuristic algorithms to successfully solve 0–1 KPs. Nevertheless, metaheuristic algorithms are generally compute intensive and slow when implemented in software. In this paper, we present an FPGA-based pipelined hardware accelerator to reduce computation time for solving large dimension 0–1 KPs using Binary Harmony Search algorithm. The proposed architecture exploits the intrinsic parallelism of population based metaheuristic algorithm and the flexibility and parallel processing capabilities of FPGAs to perform the computation concurrently thus enhancing performance. To validate the efficiency of the proposed hardware accelerator, experiments were conducted using a large number of 0–1 KPs. Comparative analysis on experimental results reveals that the proposed approach offers promising speedups of 51× – 111× as compared with a software implementation and 2× – 5× as compared with a hardware implementation of Binary Particle Swarm Optimization algorithm.     

Optimization approximation solution for regression problem based on extreme learning machine

Extreme learning machine (ELM) is one of the most popular and important learning algorithms. It comes from single-hidden-layer feedforward neural networks. It has been proved that ELM can achieve better performance than support vector machine (SVM) in regression and classification. In this paper, mathematically, with regression problem, the step 3 of ELM is studied. First of all, the equation Hβ=T are reformulated as an optimal model. With the optimality, the necessary conditions of optimal solution are presented. The equation Hβ=T is replaced by H^THβ=H^TT. We can prove that the latter must have one solution at least. Second, optimal approximation solution is discussed in cases of H is column full rank, row full rank, neither column nor row full rank. In the last case, the rank-1 and rank-2 methods are used to get optimal approximation solution. In theory, this paper present a better algorithm for ELM.     

Thread Scheduling for Multiprogrammed Multiprocessors

We present a user-level thread scheduler for shared-memory multiprocessors, and we analyze its performance under multiprogramming. We model multiprogramming with two scheduling levels: our scheduler runs at user-level and schedules threads onto a fixed collection of processes, while below this level, the operating system kernel schedules processes onto a fixed collection of processors. We consider the kernel to be an adversary, and our goal is to schedule threads onto processes such that we make efficient use of whatever processor resources are provided by the kernel. Our thread scheduler is a non-blocking implementation of the work-stealing algorithm. For any multithreaded computation with work T ₁ and critical-path length T _∈ fty , and for any number P of processes, our scheduler executes the computation in expected time O(T ₁ /P _A + T _∈ fty P/P _A ) , where P _A is the average number of processors allocated to the computation by the kernel. This time bound is optimal to within a constant factor, and achieves linear speedup whenever P is small relative to the parallelism T ₁ /T _∈ fty . Online publication February 26, 2001.     

Constructing the Simplest Possible Phylogenetic Network from Triplets

A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing so-called reticulations such as recombinations, hybridizations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network with smallest possible level in time O(|T| ^k+1), if k is a fixed upper bound on the level of the network.     

基于残差分析的GM(1,1)模型有效性研究

GM(1,1)模型是处理贫信息数据序列的有效工具,也是灰色理论体系中应用广泛、具有基础性地位的一类重要模型.从一个新的视角-残差的角度,对该模型的有效性和使用范围进行分析.结果表明,GM(1,1)除了对指数衰减趋0的序列实现+∞上的拟合外,对算术级数序列和指数增加的序列拟合效果不佳,残差分布是不均匀的,且有不断扩大的趋势.     

A dynamic Houjin (square) and a symmetric Houjin

A Houjin is an n by n square lattice with each cell containing a symbol (such as a number or a letter). Further, these numbers or letters are designed to exhibit symmetry. For example, a magic square is a Houjin where the embedded symmetry is that the numbers in each row, column, and a center diagonal have an equal sum. This article reports a new Houjin: a dynamic Houjin. A dynamic Houjin changes its numbers at each time step while satisfying the symmetry as a Houjin (a magic square). The dynamic Houjin has a further symmetry in a time dimension, i.e., the sums of the numbers in each cell are identical.     

基于二维局部保留映射的小样本掌纹识别

小样本生物识别是现实应用中一个较难解决的问题,通过有限训练样本很难得到满意的识别结果。因此,提出了一种新的小样本掌纹识别方法,利用改进的二维局部保留映射（I2DLPP）提取特征,并用支持向量机（SVM）分类。改进的二维局部保留映射是通过同时在行和列方向上进行2DPCA和2DLPP的投影实现的,从而降低了计算复杂度与特征维数;并且构建最近邻图是以图像内部的列为节点,保留更多内部流形结构,改善了识别效果。SVM是针对小样本识别的非常有效的分类工具,将两者结合可以显著提高小样本掌纹识别精度。实验结果证明了该方法的有效性。     

Optimal architectures and algorithms for mesh-connected parallelcomputers with separable row/column buses

A two-dimensional mesh of processing elements (PE's) with separable row and column buses (i.e., broadcast mechanisms for rows and columns that can be logically divided into a number of local buses through the use of PE-controlled switches) has been shown to be quite effective for semigroup computation, prefix computation, and a wide class of other computations that do not require excessive communication or data routing. For meshes with separable row/column buses, the authors show how semigroup and prefix computations can be performed with the same asymptotic time complexity without the provision of buses for every row and every column and discuss the VLSI implications of this new architecture     

Finite element modeling of Cr(VI) reduction by Shewanella oneidensis MR-1 employing the dual-enzyme kinetic model

Chromium (VI) (Cr(VI)) contamination of soil and groundwater is considered a major environmental concern. Bioreduction of Cr(VI) to chromium (III) (Cr(III)) can be considered an effective technology in remediating Cr(VI) contaminated sites. Among the Cr(VI) reducing bacteria, Shewanella oneidensis MR-1 (MR-1) is relatively effective. Reduction of Cr(VI) by MR-1 is defined by the dual-enzyme kinetic model. Existing models are not able to simulate bioreduction of Cr(VI) by employing the dual-enzyme kinetic model. The objective of this paper is to present a finite element model capable of simulating bioreduction of Cr(VI) by employing the dual-enzyme kinetic model and compare its prediction with experimental results. The model developed is accurate and can provide oscillation-free results for Peclet number Pn≤20 and Courant number Cn≤1. The model prediction compares well with the experimental results.     

Dynamic matrix rank

We consider maintaining information about the rank of a matrix under changes of the entries. For n×n matrices, we show an upper bound of O(n^1.575) arithmetic operations and a lower bound of Ω(n) arithmetic operations per element change. The upper bound is valid when changing up to O(n^0.575) entries in a single column of the matrix. We also give an algorithm that maintains the rank using O(n²) arithmetic operations per rank one update. These bounds appear to be the first nontrivial bounds for the problem. The upper bounds are valid for arbitrary fields, whereas the lower bound is valid for algebraically closed fields. The upper bound for element updates uses fast rectangular matrix multiplication, and the lower bound involves further development of an earlier technique for proving lower bounds for dynamic computation of rational functions.     

A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem

This paper presents a multiprocessor based heuristic algorithm for the Multi-dimensional Multiple Choice Knapsack Problem (MMKP). MMKP is a variant of the classical 0–1 knapsack problem, where items having a value and a number of resource requirements are divided into groups. Exactly one item has to be picked up from each group to achieve a maximum total value without exceeding the resource constraint of each type. MMKP has many real world applications including admission control in adaptive multimedia server system. Exact solution to this problem is NP-Hard, and hence is not feasible for real time applications like admission control. Therefore, heuristic solutions have been developed to solve the MMKP. M-HEU is one such heuristic, which solves the MMKP achieving a reasonable percentage of optimality. In this paper, we present a multiprocessor algorithm based on M-HEU, which runs in O(T/p+s(p)) time, where T is the time required by the algorithm using single processor, p is the number of processors and s(p), a function of p, is the synchronization overhead. We also present the worst-case analysis of our algorithm, the computation of the optimal number of processors as well as the lower bound of the total value that can be achieved by the heuristic.     

Preserving Privacy of Software-Defined Networking Policies by Secure Multi-Party Computation

In software-defined networking (SDN), controllers are sinks of information such as network topology collected from switches. Organizations often like to protect their internal network topology and keep their network policies private. We borrow techniques from secure multi-party computation (SMC) to preserve the privacy of policies of SDN controllers about status of routers. On the other hand, the number of controllers is one of the most important concerns in scalability of SMC application in SDNs. To address this issue, we formulate an optimization problem to minimize the number of SDN controllers while considering their reliability in SMC operations. We use Non-Dominated Sorting Genetic Algorithm II (NSGA-II) to determine the optimal number of controllers, and simulate SMC for typical SDNs with this number of controllers. Simulation results show that applying the SMC technique to preserve the privacy of organization policies causes only a little delay in SDNs, which is completely justifiable by the privacy obtained.

     

Lar(m,c, l) grammars

We present the class of LAR(M, C, L) context-free grammars: a generalization of several classes of fixed and arbitrary lookahead LR grammars that appear in the literature. The parser construction is based on three parameters M, C and L; M and C determine the type of parser, and L is the amount of lookahead. Specific settings of these parameters yield fixed-lookahead grammar classes such as LALR(k), SLR(k) and NQLALR, along with several arbitrary lookahead classes, all of which are subsets of LR-Regular. Thus both fixed and arbitrary lookahead LR techniques are described (and implemented) by one powerful model.     

Kernel Factory: An ensemble of kernel machines

We propose an ensemble method for kernel machines. The training data is randomly split into a number of mutually exclusive partitions defined by a row and column parameter. Each partition forms an input space and is transformed by an automatically selected kernel function into a kernel matrix K. Subsequently, each K is used as training data for a base binary classifier (Random Forest). This results in a number of predictions equal to the number of partitions. A weighted average combines the predictions into one final prediction. To optimize the weights, a genetic algorithm is used. This approach has the advantage of simultaneously promoting (1) diversity, (2) accuracy, and (3) computational speed. (1) Diversity is fostered because the individual K’s are based on a subset of features and observations, (2) accuracy is sought by automatic kernel selection and the genetic algorithm, and (3) computational speed is obtained because the computation of each K can be parallelized. Using five times twofold cross validation we benchmark the classification performance of Kernel Factory against Random Forest and Kernel-Induced Random Forest (KIRF). We find that Kernel Factory has significantly better performance than Kernel-Induced Random Forest. When the right kernel is selected Kernel Factory is also significantly better than Random Forest. In addition, an open-source R-software package of the algorithm (kernelFactory) is available from CRAN.     

A scheme for LR(k) parsing with error recovery part II: error recovery

The paper is the second in a series of three papers devoted to a detailed study of LR(k) parsing with error recovery and correction. Error recovery in LR(k) parsing of a context-free grammar is formalized by extending an LR(k) parser of the grammar such that it accepts all strings over the terminal vocabulary. The parse produced by this extension for a terminal string is a right parse if the string is in the language. In the case of a string not in the language the parse produced by the extension contains so-called error productions which represent the error recovery actions performed by the extension. The treatment is based on the formalization of LR(k) parsing presented in the first paper in the series and it covers practically all error recovery methods designed for LR(k) parsing.