On a family of pseudorandom binary sequences

Recently, numerous constructions have been given for finite pseudorandom binary sequences. However, in many applications, e.g., in cryptography one needs large families of good pseudorandom sequences. Very Recently L.~Goubin, C.~Mauduit, A.~Sárkzy succeeded in constructing large families of pseudorandom binary sequences based on the Legendre symbol. In this paper we will generate another type of large family of pseudorandom sequences by using the notion of index (discrete logarithm).     

The complexity of the word-problem for finite matrix rings

We analyze the so-called word-problem for , the ring of matrices over . We prove that the term-equivalence problem for the semigroup (and so for the ring) is coNP-complete.

     

A projected‐steepest‐descent potential‐reduction algorithm for convex programming problems

A recent work of Shi (Numer. Linear Algebra Appl. 2002; 9 : 195–203) proposed a hybrid algorithm which combines a primal‐dual potential reduction algorithm with the use of the steepest descent direction of the potential function. The complexity of the potential reduction algorithm remains valid but the overall computational cost can be reduced. In this paper, we make efforts to further reduce the computational costs. We notice that in order to obtain the steepest descent direction of the potential function, the Hessian matrix of second order partial derivatives of the objective function needs to be computed. To avoid this, we in this paper propose another hybrid algorithm which uses a projected steepest descent direction of the objective function instead of the steepest descent direction of the potential function. The complexity of the original potential reduction algorithm still remains valid but the overall computational cost is further reduced. Our numerical experiments are also reported. Copyright © 2004 John Wiley & Sons, Ltd.     

Combinatorial optimization and hierarchical classifications

This paper is devoted to some selected topics relating Combinatorial Optimization and Hierarchical Classification. It is oriented toward extensions of the standard classification schemes (the hierarchies): pyramids, quasi-hierarchies, circular clustering, rigid clustering and others. Bijection theorems between these models and dissimilarity models allow to state some clustering problems as optimization problems. Within the galaxy of optimization we have especially discussed the following: NP-completeness results and search for polynomial instances; problems solved in a polynomial time (e.g. subdominant theory); design, analysis and applications of algorithms. In contrast with the orientation to new clustering problems, the last part discusses some standard algorithmic approaches.Received: July 2004, Revised: September 2004, MSC classification: 62H30, 91C20, 05C65, 90C27, 68R01     

Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay

We consider the makespan minimization for a unit execution time task sequencing problem with a bipartite precedence delays graph and a positive precedence delay d. We prove that the associated decision problem is strongly NP-complete and we provide a non-trivial polynomial sub-case. We also give an approximation algorithm with ratio .     

On linear programs with random costs

We consider linear programs in which the objective function (cost) coefficients are independent non-negative random variables, and give upper bounds for the random minimum cost. One application shows that for quadratic assignment problems with such costs certain branch-and-bound algorithms usually take more than exponential time.     

Complexity of some natural problems on the class of computable I-algebras

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ ₁ ¹ -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ ₃ ⁰ -complete.     

Sports tournaments, home–away assignments, and the break minimization problem

We consider the break minimization problem for fixing home–away assignments in round-robin sports tournaments. First, we show that, for an opponent schedule with n teams and n−1 rounds, there always exists a home–away assignment with at most breaks. Secondly, for infinitely many n, we construct opponent schedules for which at least breaks are necessary. Finally, we prove that break minimization for n teams and a partial opponent schedule with r rounds is an NP-hard problem for r≥3. This is in strong contrast to the case of r=2 rounds, which can be scheduled (in polynomial time) without any breaks.     

教育投资问题的表上作业法

教育投资问题的表上作业法使小规模情形下的手工操作变得十分方便、迅速,而且大规模情形下更有利于计算机的实现。本还就此算法给出了实例和复杂性分析。     

Recovering signals from inner products involving prolate spheroidals in the presence of jitter

The paper deals with recovering band- and energy-limited signals from a finite set of perturbed inner products involving the prolate spheroidal wavefunctions. The measurement noise (bounded by ) and jitter meant as perturbation of the ends of the integration interval (bounded by ) are considered. The upper and lower bounds on the radius of information are established. We show how the error of the best algorithms depends on and . We prove that jitter causes error of order , where is a bandwidth, which is similar to the error caused by jitter in the case of recovering signals from samples.