A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

Petersen图的点传递正则覆盖图

运用基图自同构能被提升的线性准则 ,对满足 :1覆叠变换群 K =Znp,2覆盖图的保簇变换群是点传递的 Petersen图的连通正则覆盖图进行了完全分类 .这种图共有 1 2种类型 .     

Covering arrays of higher strength from permutation vectors

A covering array CA(N;t,k,v) is an N × k array such that every N × t sub‐array contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006     

关于某类解析函数的星象性和Ruscheweyh的一个问题

本文引入了一个涉及Ruscheweyh导数的解析函数子类，应用微分从属方法和Carlson-Shaffer算子讨论了它的从属关系和偏差定理；其次，应用单叶函数的性质和一个微分不等式研究了它的星象性条件和覆盖定理，最后，部分地解决了Ruscheweyh的一个问题。     

二元外代数的Z_n-Galois覆盖代数的Hochschild(上)同调群

设Λ是特征不整除n的域k上的二元外代数,■是Λ的Zn-Galois覆盖代数.首先构造了■的极小投射双模分解,并由此清晰地计算了■的各阶Hochschild同调和上同调群的维数;并且在域的特征为零时,计算了■的循环同调群的维数.     

Some insight into characterizations of minimally nonideal matrices

Lehman (Polyhedral combinatorics 1 of DIMACS series in discrete math. and theoretical computer science, pp 101–105, 1990) described some conditions regular minimally nonideal (mni) matrices must satisfy. Although, there are few results on sufficient conditions for mni matrices. In most of these results, the covering polyhedron must have a unique fractional extreme point. This condition corresponds to ask the matrix to be the blocker of a near-ideal matrix, defined by the authors in a previous work (2006). In this paper we prove that, having the blocker of a near-ideal matrix, only a few very easy conditions have to be checked in order to decide if the matrix is regular mni. In doing so, we define the class of quasi mni matrices, containing regular mni matrices, and we find a generalization on the number of integer extreme points adjacent to the fractional extreme point in the covering polyhedron. We also give a relationship between the covering and stability number of regular mni matrices which allows to prove when a regular mni matrix can be a proper minor of a quasi mni. Partially supported by CONICET Grant PIP 2807/2000 (Argentina) and by CNPq/PROSUL Grant 490333/2004-4 (Brasil).     

A probabilistic analysis of the set covering problem

A probabilistic analysis of the minimum cardinality set covering problem (SCP) is developed, considering a stochastic model of the (SCP), withn variables andm constraints, in which the entries of the corresponding (m, n) incidence matrix are independent Bernoulli distributed random variables, each with constant probabilityp of success. The behaviour of the optimal solution of the (SCP) is then investigated as bothm andn grow asymptotically large, assuming either an incremental model for the evolution of the matrix (for each size, the matrixA is obtained bordering a matrix of smaller size by new columns and rows) or an independent one (for each size, an entirely new set of entries forA are considered). Two functions ofm are identified, which represent a lower and an upper bound onn in order the (SCP) to be a.e. feasible and not trivial. Then, forn lying within these bounds, an asymptotic formula for the optimum value of the (SCP) is derived and shown to hold a.e.The performance of two simple randomized algorithms is then analyzed. It is shown that one of them produces a solution value whose ratio to the optimum value asymptotically approaches 1 a.e. in the incremental model, but not in the independent one, in which case the ratio is proved to be tightly bounded by 2 a.e. Thus, in order to improve the above result, a second randomized algorithm is proposed, for which it is proved that the ratio between the approximate solution value and the optimum approaches 1 a.e. also in the independent model.     

On DRC‐covering of Kn by cycles

This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on INF‐networks which are protected independently from each other. The problem can be stated as follows: for a given graph G, find a cycle covering of the edge set of K_n, where V(K_n) = V(G), such that each cycle in the covering satisfies the disjoint routing constraint (DRC7rpar;, relatively to G, which can be stated as follows: to each edge of K_n we associate in G a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint. Here we consider the case where G = C_n, a ring of size n and we want to minimize the number of cycles in the covering. We give optimal solutions for the problem as well as for variations of the problem, namely, its directed version and the case when the cycle length is fixed to 4. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 100–112, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10040     

Accelerations for global optimization covering methods using second derivatives

Two improvements for the algorithm of Breiman and Cutler are presented. Better envelopes can be built up using positive quadratic forms. Better utilization of first and second derivative information is attained by combining both global aspects of curvature and local aspects near the global optimum. The basis of the results is the geometric viewpoint developed by the first author and can be applied to a number of covering type methods. Improvements in convergence rates are demonstrated empirically on standard test functions.Partially supported by an University of Canterbury Erskine grant.     

指派问题匈牙利解法的又两个注记

本文就指派问题匈牙利解法中的一些方法提出两个注记，且为此提供一个较为简单的解法。