Coloring graphs by iterated local search traversing feasible and infeasible solutions

Graph coloring is one of the hardest combinatorial optimization problems for which a wide variety of algorithms has been proposed over the last 30 years. The problem is as follows: given a graph one has to assign a label to each vertex such that no monochromatic edge appears and the number of different labels used is minimized. In this paper we present a new heuristic for this problem which works with two different functionalities. One is defined by two greedy subroutines, the former being a greedy constructive one and the other a greedy modification one. The other functionality is a perturbation subroutine, which can produce also infeasible colorings, and the ability is then to retrieve feasible solutions. In our experimentation the proper tuning of this optimization scheme produced good results on known graph coloring benchmarks.     

非关联塑性切线刚度矩阵的对称表示

文中建议的数值方法使可能在非关联塑性切线刚度程序中采用对称解法。     

Methodological reflections on a three-step-design combining observation,stimulated recall and interview

In this paper a tripartite qualitative design combining abservation, stimulated recall and interview is presented and discussed. This three-step-design makes it possible to get insight into the interaction of internal and external processes when solving mathematical tasks. The data analysis depends on the research question and the methodological approach. In the light of two research projects in mathematics education two different methods of data analysis are presented and methodologically reflected.     

Review of Simulation Languages

The rapid acceptance of the need for special programming languages to aid in computer simulation has led to a large number of such languages in recent years. The purpose of this paper is to review the principal of these languages and to make a comparison of their characteristics. The first characteristic discussed is the method of dealing with time advance and the organization. This is followed by a discussion on the naming and structure of entities.An important aspect of simulation is the comprehensiveness of the test facilities which then receive discussion. The facilities provided by the various programs for introducing procedures or subroutines is described, with special emphasis on sampling, statistic-collecting and output procedures.Lastly, the facilities provided for development are discussed and the paper ends with a brief summary of each of the languages covered.     

Control of large flexible systems via eigenvalue relocation

For the vibration control of large flexible systems, a control scheme by which the eigenvalues of the closed-loop systems are assigned to predetermined locations within the feasible region through velocity-only feedback is presented. Owing to the properties of second-order λ-matrices and an efficient model decoupling technique, the control scheme makes it possible that selected modes are damped with the rest of the modes unchanged.     

A bisection-extreme point search algorithm for optimizing over the efficient set in the linear dependence case

The algorithms and algorithmic ideas currently available for globally optimizing linear functions over the efficient sets of multiple objective linear programs either use nonstandard subroutines or cannot yet be implemented for lack of sufficient development. In this paper a Bisection-Extreme Point Search Algorithm is presented for globally solving a large class of such problems. The algorithm finds an exact, globally-optimal solution after a finite number of iterations. It can be implemented by using only well-known pivoting and optimization subroutines, and it is adaptable to large scale problems or to problems with many local optima.     

Controlling the chaotic response to a prospective external signal using back-propagation neural networks

For a chaotic system, a control scheme is presented, based on the back-propagation neural network (BPNN). The scheme can control the chaotic response to a prospective external signal, which can be periodic, nonlinear or even a non-analytical discontinuous function. For a chaotic system with high dimensions, each variable can be controlled for the different signals. For Lorenz, Rossler and Duffing systems, simulations are carried out and the proposed scheme is proved to be effective within a short control time.     

对数函数和指数函数的子程序方案

本文提供了在电子计算机上应用的计算lnx的两个子程序方案和e~x的一个子程序方案,它们所需的运算量较为节省。文章描述了方案选择和计算处理的细节,并对选定的方案给出了相应的误差分析和估计。     

Non-uniform multiresolution analysis with supercompact multiwavelets

This work is devoted to a generalization of the framework presented in Beam and Warming (2000) [6], where a multiresolution analysis scheme with supercompact multiwavelets was presented. The approach considers uniform partitions of a nested grid hierarchy in the framework of Harten’s multi-scale representations. In this paper we study the non-uniform case. The non-uniform analysis is well adapted to more realistic contexts and makes it possible to improve the approximation.     

Pseudoclassical Foldy-Wouthuysen transformation and canonical quantization of (D=2n)-dimensional relativistic particle with spin in an external electromagnetic field

The canonical quantization of a (D=2n)-dimensional Dirac particle with spin in an arbitrary external electromagnetic field is performed in a gauge that makes it possible to describe simultaneously particles and antiparticles (both massive and massiess) already at the classical level. A pseudoclassical Foldy-Wouthuysen transformation is used to find the canonical (Newton-Wigner) coordinates. The connection between this quantization scheme and Blount's picture describing the behavior of a Dirac particle in an external electromagnetic field is discussed.Erevan Physics Institute. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 102, No. 3, pp. 378–383, March, 1995.     

Restorations of punctured languages and similarity of languages

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ ‐similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non‐slender linear languages. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Finding the response matrix to the external action from a subspace for a discrete linear stochastic dynamical system

For a discrete linear stochastic dynamical system, computation of the response matrix to the external action from a subspace using given observational data is examined. An algorithm is proposed and substantiated that makes it possible to improve the numerical accuracy and to reduce the amount of observational data compared to the general case where an arbitrary external action is allowed. As an illustration, a discrete system arising in the analysis of a linear stochastic dynamical continuous-time system is considered more thoroughly. Some numerical results are presented.     

Fortran codes for computing the discrete Helmholtz integral operators

In this paper Fortran subroutines for the evaluation of the discrete form of the Helmholtz integral operators L _k, M _k, M _k ^t and N _k for two-dimensional, three-dimensional and three-dimensional axisymmetric problems are described. The subroutines are useful in the solution of Helmholtz problems via boundary element and related methods. The subroutines have been designed to be easy to use, reliable and efficient. The subroutines are also flexible in that the quadrature rule is defined as a parameter and the library functions (such as the Hankel, exponential and square root functions) are called from external routines. The subroutines are demonstrated on test problems arising from the solution of the Neumann problem exterior to a closed boundary via the Burton and Miller equation. This revised version was published online in August 2006 with corrections to the Cover Date.     

An entire strategy for precise system tracking control of a revolving thin flexural link,part I: Finite element modeling and direct tuning controller design

An entire control strategy including a design based model, controller design, and system output modification for a distributed parameter system is illuminated by application to feedback control of a revolving thin flexural link. In Part I, a very realizable actuator and a sensor, which uses a motor and a tachometer, are applied to design the control system. The finite element modeling and the state space representation are obtained for the purpose of control system analysis and computer simulation. Instead of relying on parameter identification subroutines, a controller design based on directly tuning the parameter of the gain makes the closed-loop absolutely stable and good for system tracking control. This control system design scheme is robust, insensitive to system parameter changes, and this algorithm cannot depend on traditionally priori knowledge such as the system dimension, exact model, or observer design. The performance included in the presence of all the high frequency dynamics can be effectively shown through the computer simulation, and one is led to speculate that this design scheme may perform quite well in the real world implementation.     

体模型的一种细分格式

In this paper, a subdivision scheme which generalizes a surface scheme in previous papers to volume meshes is designed. The scheme exhibits significant control over shrink-age/size of volumetric models. It also has the ability to conveniently incorporate boundaries and creases into a smooth limit shape of models. The method presented here is much simpler and easier as compared to MacCracken and Joy‘s. This method makes no restrictions on the local topology of meshes. Particularly, it can be applied without any change to meshes of nonmanifold topology.     

A BRANCH BOUND METHOD FOR SUBSET SUM PROBLEM

ＡＢＲＡＮＣＨＢＯＵＮＤＭＥＴＨＯＤＦＯＲＳＵＢＳＥＴＳＵＭＰＲＯＢＬＥＭＷＵＳＨＩＱＵＡＮ（吴士泉）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，Ｃ...     

Computational experience with a group theoretic integer programming algorithm

This paper gives specific computational details and experience with a group theoretic integer programming algorithm. Included among the subroutines are a matrix reduction scheme for obtaining group representations, network algorithms for solving group optimization problems, and a branch and bound search for finding optimal integer programming solutions. The innovative subroutines are shown to be efficient to compute and effective in finding good integer programming solutions and providing strong lower bounds for the branch and bound search.This research was supported in part by the U.S. Army Research Office (Durham) under contract no. DAHC04-70-C-0058. This paper is not an official National Bureau of Economic Research publication.