Almost zeros of a set of polynomials of R[s]

The notion of an exact zero of a sot of polynomials p of R[s] is extended to that of an almost zero. The almost zeros are defined as minima of a norm function of p and their invariance under a. certain equivalence relation &, defined on p, is established, The region of the complex plane which contains the prime almost zero (global minimum) is defined, and necessary and sufficient conditions characterizing the set of almost zeros are given. The role of almost zeros of p in the zero assignment problem of the combinants of p is investigated. Under the assumption of non-assignability for p, it is shown that the almost zeros act as nearly fixed zeros of the combinants. Every almost zero z is the centre of a disc D(z, R) which contains at least one zero of all combinants of p. The size of the radius R of this disc provides a measure of the ability of the almost zero to attract the zeros of the combinants of p A number of results for estimating upper bounds for the radius R, associated with subfamilies of the general family of combinants of p, are given. Finally, a sufficient condition for estimating an upper bound for the disc D(z, R) which contains at least one zero of all combinants of P is derived. The paper provides a more meaningful definition, from the numerical point of view, for the non-generic notion of a zero of a set of polynomials ; it also shows how some of the properties of a zero extend naturally to the almost zero case.     

Assigning the set of zeros in control systems with parallel compensation

The problem of ensuring a given set of zeros in a linear multivariable dynamical system with the equal number of inputs and outputs that includes a parallel compensator and feedback loop is considered. Methods reducing this problem to the control of eigenvalues of a certain matrix are proposed; the simultaneous assignment of poles and zeros is reduced to the control of poles of two plants using a single controller. The calculations are based on well-known and well-tested modal control techniques.     

Two algorithms for determining a minimum independent dominating set

The problem of determining a minimum independent dominating set is fundamental to both the theory and applications of graphs. Computationally it belongs to the class of hard combinatorial optimization problems known as NP-hard. In this paper, we develop a backtracking algorithm and a dynamic programming algorithm to determine a minimum independent dominating set. Computational experience with the backtracking algorithm on more than 1000 randomly generated graphs ranging from 100 to 200 vertices and from 10% to 60% densities has shown that the algorithm is effective.     

Features of the deterministic replay in the case of a minimum device set

A technology of the deterministic replay of an execution process in virtual machines can be used for debugging, improving reliability and robustness, software development and incident investigation (including reverse engineering of malware). The paper describes an implementation of deterministic replay for guest machines based on IA-32 in the emulator QEMU. This implementation minimizes the list of replayed devices. The organization of QEMU is discussed in detail, and the techniques used in the implementation are thoroughly explained. The key performance characteristics, such as the size of log of nondeterministic events and slowdown are experimentally measured.     

求极小碰集的蛛网算法

为降低空间复杂度和减少搜索时间,结合极小碰集的特点和生物学中蜘蛛捕食思想,提出了一种搜索极小碰集的蛛网算法。该方法考虑集合之间的相关性,并构造能在蛛网上寻路的访问蜘蛛用于寻找蛛网内集合的所有极小碰集。在该算法中,所提出的访问蜘蛛生成和搜索策略能够降低空间复杂度和减少搜索时间。将此算法与其他的极小碰集算法进行比较,实验结果表明,该算法在保证得到所有极小碰集的前提下,具有较低的空间复杂度和较高的时间效率。     

On the determination of the number and multiplicity of zeros of a function

It is shown that certain simple integrals determine the number of zeros with a certain multiplicity of a function of one variable in an arbitrary interval. Several typical numerical examples are given.     

Enumeration of all minimum feedback edge sets in a directed graph

The purpose of the present paper is to propose an efficient algorithm to enumerate all the minimum feedback edge sets of a given directed graph. The algorithm has been developed in two distinct phases, i.e. all the directed circuits of the given graph are generated at the first phase and then the minimum feedback edge sets are determined from the information of the directed circuits. The proposed algorithm offers easy programmability on a digital computer, and it seems economic in terms of computation time and required storage space.     

禁忌遗传算法求解最小支配集

如何寻找一个网络图的最小支配集是NP难题。分别设计了逆序启发式算法和禁忌搜索算法,并在此基础上提出了禁忌遗传算法（TSGA）用于求解最小支配集;将禁忌搜索和遗传算法结合起来,弥补了彼此的不足,既有效地避免了算法易陷入局部最优解的缺陷,又加快了算法的收敛速度。经对大量随机网络图的测试和对物流网络选址问题的求解,验证了TSGA算法的优越性。     

A note on transmission zeros of a transfer function matrix

A new proof is provided to show that the numerator polynomials of the Smith-McMillan form of a rational transfer function matrix are the same as the invariant factors of a mapsI-A_{t}, with Ata map determined from the system state equations.     

On the minimum time function and the minimum energy problem; a nonlinear case

For a semilinear control system in general Banach spaces, we prove results on exact and approximate controllability, regularity of the minimum time function, connections between the minimum time function and the minimum energy.     

A minimum adequate set of multi-valued logic

An adequate set of k-valued logic is provided, which contains only two operators. It is also proved that this adequate set is of minimum size.     

Markov decision processes with a target set for minimum criteria

We consider Markov decisions processes with a target set, where criterion function is an expectation of minimum function. We formulate the problem as an infinite horizon case with a recurrent class. We show under some conditions that an optimal value function is a unique solution to an optimality equation and there exists a stationary optimal policy. Also we give a policy improvement method.     

Extracting maximal information about sets of minimum cuts

There are two well-known, elegant, compact, and efficiently computed representations of selected minimum edge cuts in a weighted, undirected graphG=(V, E) withn nodes andm edges: at one extreme, the Gomory-Hu cut tree [12] represents minimum cuts, one for each pair of nodes inG; at the other extreme, the Picard-Queyranne DAG [24] represents all the minimum cuts between a single pair of nodes inG. The GH cut tree is constructed with onlyn–1 max-flow computations, and the PQ DAG is constructed with one max-flow computation, plusO(m) additional time. In this paper we show how to marry these two representations, getting the best features of both. We first show that we can construct all DAGs, one for each fixed pair of nodes, using onlyn–1 max-flow computations as in [12], plusO(m) time per DAG as in [24]. This speeds up the obvious approach by a factor ofn. We then apply this approach to an unweighted graphG, to find all the edge-connectivity cuts inG, i.e., cuts with capacity equal to the connectivity ofG. Matula [22] gave a method to find one connectivity cut inO(nm) time; we show thatO(nm) time suffices to represent all connectivity cuts compactly, and to list all of them explicitly. This improves the previous best time bound ofO(n ² m) [3] for listing the connectivity cuts. The connectivity cuts are central in network reliability calculations. We then show how to find all pairs of nodes that are separated by at least one connectivity cut inO(nm) time.Research was partially supported by Grant CCR-8803704 from the National Science Foundation.     

A genetic algorithm for the minimum generating set problem

Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinatorial number theory and is related to some real-world problems, such as planning radiation therapies.We present a new formulation to this problem (based on the terminology for the multiple knapsack problem) that is used to design an evolutionary approach whose performance is driven by three search strategies; a novel random greedy heuristic scheme that is employed to construct initial solutions, a specialized crossover operator inspired by real-parameter crossovers and a restart mechanism that is incorporated to avoid premature convergence. Computational results for problem instances involving up to 100,000 elements show that our innovative genetic algorithm is a very attractive alternative to the existing approaches.     

最小碰集问题的精确快速算法

为了有效解决最小碰集问题,基于分支约减技术提出了一个相对简单的递归算法.同时使用新近提出的一种称为度量与分治的方法,通过对问题实例规模进行加权,建立非标准的度量,对算法进行了分析,并与标准的分析方法做了比较.在分析过程中,为了优化权值以获得更好的算法时间复杂度,使用了一种成功应用于回溯算法分析的数学规划方法--拟凸规划,对建立的问题实例规模新度量中的权值进行了优化,最终证明了该算法可以在使用多项式空间情况下,在O(1.23801")时间内解决最小碰集问题.     

New minimum sigma set for unscented filtering

In this work, a new minimum set of sigma points for unscented filtering is proposed along with its unscented Kalman filter in both square‐root and nonsquare‐root forms. Comparative with the other reduced sigma sets of the literature, the new sigma set is, in some cases, better defined or, in another case, a generalization. In numerical examples, the unscented transform of the new sigma set is compared with the unscented transforms of the other reduced sigma sets of the literature. In addition, the performance of the new unscented Kalman filter is studied in an aircraft target tracking scenario. Copyright © 2014 John Wiley & Sons, Ltd.