Search games with immobile hider

In this paper we discuss a type of search game with immobile hider on a graph. If the graph is weakly cyclic (i.e. no edge lies on two different cycles) we determine the value of the game and give an easy way to compute optimal strategies for the players. The value is half the length of a quasi-Euler path, i.e. a closed path of minimal length that visits all points of the network.     

Use of the Minimum-Norm Search Direction in a Nonmonotone Version of the Gauss-Newton Method

In this work, a new stabilization scheme for the Gauss-Newton method is defined, where the minimum norm solution of the linear least-squares problem is normally taken as search direction and the standard Gauss-Newton equation is suitably modified only at a subsequence of the iterates. Moreover, the stepsize is computed by means of a nonmonotone line search technique. The global convergence of the proposed algorithm model is proved under standard assumptions and the superlinear rate of convergence is ensured for the zero-residual case. A specific implementation algorithm is described, where the use of the pure Gauss-Newton iteration is conditioned to the progress made in the minimization process by controlling the stepsize. The results of a computational experimentation performed on a set of standard test problems are reported.     

Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

椭圆曲线素阶群上的离散对数求解

该文对解椭圆曲线上离散对数的Pollard ρ算法和并行碰撞搜索算法分别建立了它 们的图论模型和分析了碰撞技巧,比较了两个算法,进而提出了设计迭代函数的准则并 给出一个改进的并行碰撞算法.     

Backtracking Adaptive Search: Distribution of Number of Iterations to Convergence

Backtracking adaptive search is a simplified stochastic optimiza-tion procedure which permits the acceptance of worsening objective function values. It generalizes the hesitant adaptive search, which in turn is a gener-alization of the pure adaptive search. In this paper, we use ideas from the theory of stochastic processes to determine the full distribution of the number of iterations to convergence for the backtracking adaptive search.Communicated by P. M. PardalosThe authors thank theMarsden Fund of the Royal Society of New Zealand for support of this research. The fourth author was supported by a Bright Future Scholarship administered by the Foundation for Research, Science and Technology.     

"大互联网梅森素数寻求(GIMPS)"研究计划进展

梅森素数是一种特殊的素数,它的研究与寻求一直是数论研究的代表性问题之一.寻求梅森素数之路艰辛曲折,其计算复杂性对现代计算能力极具挑战.计算机网络技术的发展,特别是能使虚拟组织共享计算资源的全球分布计算技术,使得寻求速度大大加快.本文综述寻求梅森素数的最新进展及历史进程,并介绍寻求梅森数所用的分布计算技术.     

Optimization with additional variables and constraints

Norton, Plotkin and Tardos proved that—loosely spoken, an LP problem is solvable in time O(Tq^k+1) if deleting k fixed columns or rows, we obtain a problem which can be solved by an algorithm that makes at most T steps and q comparisons. This paper improves this running time to O(Tq^k).     

线性约束凸规划内点法及其修正算法

凸规划的内点算法是目前较热门的课题之一，参考资料[2]；[3]等均给出了较深入的研究．本文在参考前人的工作前提下，提出了带线性约束凸规划的内点算法结论（定理2．8）及相应算法．另外，木文定义了偏移因子，偏移因子对的概念，对下降方向作出了修正，并给出了相关算法．     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.