A technique to construct symmetric variable-stepsize linear multistep methods for second-order systems

Some previous works show that symmetric fixed- and variable-stepsize linear multistep methods for second-order systems which do not have any parasitic root in their first characteristic polynomial give rise to a slow error growth with time when integrating reversible systems. In this paper, we give a technique to construct variable-stepsize symmetric methods from their fixed-stepsize counterparts, in such a way that the former have the same order as the latter. The order and symmetry of the integrators obtained is proved independently of the order of the underlying fixed-stepsize integrators. As this technique looks for efficiency, we concentrate on explicit linear multistep methods, which just make one function evaluation per step, and we offer some numerical comparisons with other one-step adaptive methods which also show a good long-term behaviour.

     

On quasi-solution to infeasible linear complementarity problem obtained by Lemke’s method

For a linear complementarity problem with inconsistent system of constraints a notion of quasi-solution of Tschebyshev type is introduced. It’s shown that this solution can be obtained automatically by Lemke’s method if the constraint matrix of the original problem is copositive plus or belongs to the intersection of matrix classes P ₀ and Q ₀.     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

一般线性模型下方差最小范数二次无偏估计的稳健性

本文给出了一般线性模型下,由最小二乘得到的方差估计与最小范数二次无偏估计相等的充分必要条件,并且当Gauss-Markov估计与最小二乘估计相等时,可以得到一个简单的等价条件。     

On the Global Stability of Solutions of Moment Systems in Nonequilibrium Thermodynamics

In this paper, we study the linearization of the Cauchy problem and the mixed problem for the system of Grad--Hermite moments in nonequilibrium thermodynamics in the neighborhood of the equilibrium state. Stability conditions for solutions of the Cauchy problem are proved as a generalization of the classical Hermite--Biller theorem on stable polynomials. For the mixed problem, we prove an analog of the Vishik--Lyusternik theorem on small singular perturbations of general elliptic problems. The last observation allows us to introduce the Shapiro--Lopatinskii condition, which implies the well-posedness of the mixed problem.     

A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

Existence and characterization of regions minimizing perimeter under a volume constraint inside Euclidean cones

We study the problem of existence of regions separating a given amount of volume with the least possible perimeter inside a Euclidean cone. Our main result shows that nonexistence for a given volume implies that the isoperimetric profile of the cone coincides with the one of the half-space. This allows us to give some criteria ensuring existence of isoperimetric regions: for instance, local convexity of the cone at some boundary point.

We also characterize which are the stable regions in a convex cone, i.e., second order minima of perimeter under a volume constraint. From this it follows that the isoperimetric regions in a convex cone are the euclidean balls centered at the vertex intersected with the cone.

     

直径不超过4的树的割宽

§ 1　IntroductionThe cutwidth problem for graphs,as well as a class of optimal labeling and embed-ding problems,have significant applications in VLSI designs,network communicationsand other areas (see [2 ] ) .We shall follow the graph-theoretic terminology and notation of [1 ] .Let G=(V,E)be a simple graph with vertex set V,| V| =n,and edge set E.A labeling of G is a bijec-tion f:V→ { 1 ,2 ,...,n} ,which can by regarded as an embedding of G into a path Pn.Fora given labeling f of G,th…     

关于解椭圆型问题的多子域D-N交替算法

构造一个求解椭圆型边值问题的多子域D—N交替算法，导出对应的容度方程和等价的迭代法，证明算法的收敛性。     

Local automorphisms of operator algebras on Banach spaces

In this paper we extend a result of Semrl stating that every 2-local automorphism of the full operator algebra on a separable infinite dimensional Hilbert space is an automorphism. In fact, besides separable Hilbert spaces, we obtain the same conclusion for the much larger class of Banach spaces with Schauder bases. The proof rests on an analogous statement concerning the 2-local automorphisms of matrix algebras for which we present a short proof. The need to get such a proof was formulated in Semrl's paper.