A note on the Consecutive Ones Submatrix problem

A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1's consecutive in every column. The problem of Consecutive Ones Property for a matrix is a special variant of Consecutive Ones Submatrix problem in which a positive integer K is given and we want to know if there exists a submatrix B of A consisting of K columns of A with C1P property. This paper presents an error in the proof of NP-completeness for this problem in the reference cited in text by Garey and Johnson [Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979].     

The vulnerability of geometric sequences based on fields of odd characteristic

A new method of cryptologic attack on binary sequences is given, using their linear complexities relative to odd prime numbers. We show that, relative to a particular prime number p, the linear complexity of a binary geometric sequence is low. It is also shown that the prime p can be determined with high probability by a randomized algorithm if a number of bits much smaller than the linear complexity is known. This determination is made by exploiting the imbalance in the number of zeros and ones in the sequences in question, and uses a new statistical measure, the partial imbalance.This project was sponsored by the National Security Agency under Grant No. MDA904-91-H-0012. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.     

一种快速中值滤波算法在集装箱检查系统中的应用

讨论了一种新的中值滤波算法，有效地降低了传统中值滤波算法的时间复杂度，提高了计算效率和运算速度。该算法在大型集装箱检查图像处理中的应用，取得了良好的效果，提高了图像处理的速度，增强了图像处理的实时性。     

Disentangling the Sources of Opioid Withdrawal Responses: Comment on McDonald and Siegel (2004).

R. V. McDonald and S. Siegel (see record 2004-10475-001) present new evidence for the idea that opioid drug-opposite responses can become conditioned to cues of initial drug onset and that they could, therefore, play a role in the development of tolerance of some drug effects and a role in the elicitation of withdrawal-like symptoms in cases in which addicted individuals are exposed to small doses of the drug they normally consume. In this comment, some puzzling features of the data are discussed, and alternative explanations are suggested. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

求解机械装配规划的新方法

本文提出一个求解机械装配规划的算法,其计算量～O(sN~2),其中s是零件所有可能装配方向的个数,N是工件的零件数(一般s～O(N)).而现行的求机械装配规划的算法,其计算量均随N的增加按指数律增加.     

Fast algorithms for computing the diameter of a finite planar set

Three algorithms for computing the diameter of a finite planar set are proposed. Although all three algorithms have (O(n ²) worst-case running time, an expected-complexity analysis shows that, under reasonable probabilistic assumptions, all three algorithms have linear expected running time. Experimental results indicate that two of these algorithms perform very well for some distributions, and are competitive with an existing method. Finally, we exhibit situations where these exact algorithms out-perform a published approximate algorithm.Research of the first author was supported by grant NSERC A 2422. Research of the second author was supported by grants NSERC A 9293, FCAC EQ-1678 and a Killam Senior Research Fellowship awarded by the Canada Council     

Minimizing the number of tool switches on a flexible machine

This article analyzes a tool switching problem arising in certain flexible manufacturing environments. A batch of jobs have to be successively processed on a single flexible machine. Each job requires a subset of tools, which have to be placed in the tool magazine of the machine before the job can be processed. The tool magazine has a limited capacity, and, in general, the number of tools needed to produce all the jobs exceeds this capacity. Hence, it is sometimes necessary to change tools between two jobs in a sequence. The problem is then to determine a job sequence and an associated sequence of loadings for the tool magazine, such that the total number of tool switches is minimized. This problem has been previously considered by several authors; it is here revisited, both from a theoretical and from a computational viewpoint. Basic results concerning the computational complexity of the problem are established. Several heuristics are proposed for its solution, and their performance is computationally assessed.     

Local and global deadlock-detection in component-based systems are NP-hard

Interaction systems are a formal model for component-based systems. Combining components via connectors to form more complex systems may give rise to deadlock situations. We present here a polynomial time reduction from 3-SAT to the question whether an interaction system contains deadlocks.     

Optimal implementations of UPGMA and other common clustering algorithms

In this work we consider hierarchical clustering algorithms, such as UPGMA, which follow the closest-pair joining scheme. We survey optimal O(n²)-time implementations of such algorithms which use a ‘locally closest’ joining scheme, and specify conditions under which this relaxed joining scheme is equivalent to the original one (i.e. ‘globally closest’).