Multiobjective routing problems

Summary Many network routing problems, particularly where the transportation of hazardous materials is involved, are multiobjective in nature; that is, it is desired to optimise not only physical path length but other features as well. Several such problems are defined here and a general framework for multiobjective routing problems is proposed. The notion of “efficient solution” is defined and it is demonstrated, by means of an example, that a problem may have very many solutions which are efficient. Next, potentially useful solution methods for multiobjective routing problems are discussed with emphasis being placed on the use of shortest/k-shortest path techniques. Finally, some directions for possible further research are indicated. Invited by B. Pelegrin     

Globally optimal solutions of max–min systems

A variety of problems in computer science, operations research, control theory, etc., can be modeled as non-linear and non-differentiable max–min systems. This paper introduces the global optimization into such systems. The criteria for the existence and uniqueness of the globally optimal solutions are established using the high matrix, optimal max-only projection set and k ^s -control vector of max–min functions. It is also shown that the global optimization can be accomplished through the partial max-only projection representation with algebraic and combinatorial features. The methods are constructive and lead to an algorithm of finding all globally optimal solutions.     

Robust H ∞ control for singular systems with time-varying uncertainties

In this paper, we investigate the problem of robust H _∞ control for singular systems with polytopic time-varying parameter uncertainties. By introducing the notion of generalized quadratic H _∞ performance, the relationship between the existence of a robust H _∞ dynamic state feedback controller and that of a robust H _∞ static state feedback controller is given. By using matrix inequalities, the existence conditions of robust H _∞ static state feedback and dynamic output feedback controllers are derived. Moreover, the design methods for such controllers are provided in terms of the solutions of matrix inequalities. An example is also presented to demonstrate the validity of the proposed methods. __________ Translated from Journal of Northeastern University (Natural Science), 2004, 25(2): 110–113     

Asymptotically recurrent solutions ofβ-differential equations

In the paper methods from the theory of extensions of dynamical systems are used to studyβ-differential equations whose solutions possess the uniqueness property and depend continuously on the initial data and on the right-hand side of the equation. The Zhikov-Bronshtein theorems concerning asymptotically almost periodic solutions of ordinary differential equations are extended toβ-differential equations (in particular, to total differential equations). Along with asymptotic almost periodicity, we also consider asymptotic recurrence, weak asymptotic distality, and asymptotic distality. To the equations we associate dynamical systems generated by the space of the right-hand sides and the spaces of the solutions and of the initial data of solutions of the equation. Generally, the phase semigroups of the dynamical systems are not locally compact. Translated fromMatermaticheskie Zametki, Vol. 67, No. 6, pp. 837–851, June, 2000.     

Computational aspects of continuous–discrete extended Kalman-filtering

This paper elaborates how the time update of the continuous–discrete extended Kalman-filter (EKF) can be computed in the most efficient way. The specific structure of the EKF-moment differential equations leads to a hybrid integration algorithm, featuring a new Taylor–Heun-approximation of the nonlinear vector field and a modified Gauss–Legendre-scheme, generating positive semidefinite solutions for the state error covariance. Furthermore, the order of consistency and stability behavior of the outlined procedure is investigated. The results are incorporated into an algorithm with adaptive controlled step size, assuring a fixed numerical precision with minimal computational effort.     

Lp-Lq DECAY ESTIMATES FOR HYPERBOLIC EQUATIONS WITH OSCILLATIONS IN COEFFICIENTS

This work is concerned with the proof of Lp -Lq decay estimates for solutions of the Cauchy problem for utt -λ2(t)b2(t)/Δu =0. The coefficient consists of an increasing smooth function λ and an oscillating smooth and bounded function b which are uniformly separated from zero. The authors‘ main interest is devoted to the critical case where one has an interesting interplay between the growing and the oscillating part.     

Large time behavior of solutions for critical and subcritical complex Ginzburg-Landau equations in H<Superscript>1</Superscript>

Considering the Cauchy problem for the critical complex Ginzburg-Landau equation in H¹(Rⁿ), we shall show the asymptotic behavior for its solutions in C(0, ∖;H¹(Rⁿ)) ∩ L²(0, ∖;H^1,2n/(n-2)(R²)), n≥3. Analogous results also hold in the case that the nonlinearity has the subcritical power in H¹(Rⁿ), n≥1. Dedicated to Professor Zhou Yulin for his 80th birthday.     

W 2,p -a priori estimates for the emergent Poincaré Problem

We derive W ^2,p (Ω)-a priori estimates with arbitrary p ∈(1, ∞), for the solutions of a degenerate oblique derivative problem for linear uniformly elliptic operators with low regular coefficients. The boundary operator is given in terms of directional derivative with respect to a vector field ℓ that is tangent to ∂Ω at the points of a non-empty set ε ⊂ ∂Ω and is of emergent type on ∂Ω.      

On the existence of solutions for nonlinear impulsive periodic viable problems

In this paper we prove the existence of periodic solutions for nonlinear impulsive viable problems monitored by differential inclusions of the type x′(t)∈F(t,x(t))+G(t,x(t)). Our existence theorems extend, in a broad sense, some propositions proved in [10] and improve a result due to Hristova-Bainov in [13].     

含临界指数p-Kirchhoff型方程的非平凡解

本文研究了一类含临界指数的p-Kirchhoff型方程.利用变分方法与集中紧性原理,通过证明对应的能量泛函满足局部的(PS)_c条件,得到了这类方程非平凡解的存在性,推广了关于Kirchhoff型方程的相关结果.     

Stability Conditions of the MMAP [ K ]/ G [ K ]/1/ LCFS Preemptive Repeat Queue

In this paper, we study the stability conditions of the MMAP[K]/G[K]/1/LCFS preemptive repeat queue. We introduce an embedded Markov chain of matrix M/G/1 type with a tree structure and identify conditions for the Markov chain to be ergodic. First, we present three conventional methods for the stability problem of the queueing system of interest. These methods are either computationally demanding or do not provide accurate information for system stability. Then we introduce a novel approach that develops two linear programs whose solutions provide sufficient conditions for stability or instability of the queueing system. The new approach is numerically efficient. The advantages and disadvantages of the methods introduced in this paper are analyzed both theoretically and numerically.     

The Existence and Uniqueness of Nash Equilibrium Point in an m-player Game “Shoot Later, Shoot First!”

We consider the following “silent duel” of m players with a possible economic interpretation. Each player has one “bullet”, which she can shoot at any time during the time interval [0,1]. The probability that the i-th player hits the “target” at moment t is given by an increasing accuracy function f _i (t). The winner is the player who hits the target first. Under natural assumptions on the functions f _i (t) we prove the existence and uniqueness of a Nash equilibrium point in this game, and we provide an explicit construction of this equilibrium. This construction allows us to obtain exact solutions for many specific examples. Some of them are presented.This work was partly supported by RBRF grants 03-01-00479.     

Analyticity of solutions of analytic non-linear general elliptic boundary value problems, and some results about linear problems

The main aim of this paper is to discuss the problem concerning the analyticity of the solutions of analytic non-linear elliptic boundary value problems. It is proved that if the corresponding first variation is regular in Lopatinskiĭ sense, then the solution is analytic up to the boundary. The method of proof really covers the case that the corresponding first variation is regularly elliptic in the sense of Douglis-Nirenberg-Volevich, and hence completely generalize the previous result of C. B. Morrey. The author also discusses linear elliptic boundary value problems for systems of elliptic partial differential equations where the boundary operators are allowed to have singular integral operators as their coefficients. Combining the standard Fourier transform technique with analytic continuation argument, the author constructs the Poisson and Green’s kernel matrices related to the problems discussed and hence obtain some representation formulae to the solutions. Some a priori estimates of Schauder type and L _p type are obtained. __________ Translated from Acta Sci. Natur. Univ. Jilin, 1963, (2): 403–447 by GAO Wenjie.     

On balking from an empty queue

The intuition while observing the economy of queueing systems, is that one’s motivation to join the system, decreases with its level of congestion. Here we present a queueing model where sometimes the opposite is the case. The point of departure is the standard first-come first-served single server queue with Poisson arrivals. Customers commence service immediately if upon their arrival the server is idle. Otherwise, they are informed if the queue is empty or not. Then, they have to decide whether to join or not. We assume that the customers are homogeneous and when they consider whether to join or not, they assess their queueing costs against their reward due to service completion. As the whereabouts of customers interact, we look for the (possibly mixed) join/do not join Nash equilibrium strategy, a strategy that if adopted by all, then under the resulting steady-state conditions, no one has any incentive not to follow it oneself. We show that when the queue is empty then depending on the service distribution, both ‘avoid the crowd’ (ATC) and ‘follow the crowd’ (FTC) scenarios (as well as none-of-the-above) are possible. When the queue is not empty, the situation is always that of ATC. Also, we show that under Nash equilibrium it is possible (depending on the service distribution) that the joining probability when the queue is empty is smaller than it is when the queue is not empty. This research was supported by The Israel Science Foundation Grant No. 237/02.     

Heuristic Methods for Large Centroid Clustering Problems

This article presents new heuristic methods for solving a class of hard centroid clustering problems including the p-median, the sum-of-squares clustering and the multi-source Weber problems. Centroid clustering is to partition a set of entities into a given number of subsets and to find the location of a centre for each subset in such a way that a dissimilarity measure between the entities and the centres is minimized. The first method proposed is a candidate list search that produces good solutions in a short amount of time if the number of centres in the problem is not too large. The second method is a general local optimization approach that finds very good solutions. The third method is designed for problems with a large number of centres; it decomposes the problem into subproblems that are solved independently. Numerical results show that these methods are efficient—dozens of best solutions known to problem instances of the literature have been improved—and fast, handling problem instances with more than 85,000 entities and 15,000 centres—much larger than those solved in the literature. The expected complexity of these new procedures is discussed and shown to be comparable to that of an existing method which is known to be very fast.     

Asymptotic behavior of the solutions of the p -Laplacian equation

The asymptotic behavior of the solutions for p-Laplacian equations as p → ∞ is studied.     

Noncommutative Grassmannian <Emphasis Type="Italic">U</Emphasis>(1) sigma model and a Bargmann-Fock space

We consider a Grassmannian version of the noncommutative U(1) sigma model specified by the energy functional E(P) = ‖[a, P]‖ _HS ² , where P is an orthogonal projection operator in a Hilbert space H and a: H → H is the standard annihilation operator. With H realized as a Bargmann-Fock space, we describe all solutions with a one-dimensional range and prove that the operator [a, P] is densely defined in H for a certain class of projection operators P with infinite-dimensional ranges and kernels. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 153, No. 3, pp. 347–357, December, 2007.     

Asymptotic behavior of a linear difference equation with continuous time

We consider a class of linear homogeneous difference equations with constant coefficients and commensurate delays. We prove an asymptotic formula for the solutions as t → ∞ under the assumption of the existence of a simple “dominant” real characteristic value. Research supported by FONDECYT Grant, Chile, No. 1.070.980.     

The optimal convergence of the h–p version of the boundary element method with quasiuniform meshes for elliptic problems on polygonal domains

In the framework of the Jacobi-weighted Besov spaces, we analyze the lower and upper bounds of errors in the h–p version of boundary element solutions on quasiuniform meshes for elliptic problems on polygons. Both lower bound and upper bound are optimal in h and p, and they are of the same order. The optimal convergence of the h–p version of boundary element method with quasiuniform meshes is proved, which includes the optimal rates for h version with quasiuniform meshes and the p version with quasiuniform degrees as two special cases. Dedicated to Professor Charles Micchelli on the occasion of his sixtieth birthday Mathematics subject classification (2000) 65N38. Benqi Guo: The work of this author was supported by NSERC of Canada under Grant OGP0046726 and was complete during visiting Newton Institute for Mathematical Sciences, Cambridge University for participating in special program “Computational Challenges in PDEs” in 2003. Norbert Heuer: This author is supported by Fondecyt project No. 1010220 and by the FONDAP Program (Chile) on Numerical Analysis. Current address: Mathematical Sciences, Brunel University, Uxbridge, U.K.     

Partial decay on simple manifolds

Existence, uniqueness and weighted regularity of solutions of linear and nonlinear second-order uniformly elliptic differential equations on complete punctured compact N-manifolds, N > 2. Application to prescribed curvature problems: scalar curvature in a quasi-isometry class (including a contribution to the Lichnérowicz-York equation of General Relativity); Ricci curvature in a weighted Kähler class (with a related result in equiaffine geometry). A new asymptonic behaviour is allowed throughout, called partial decay, which requires its own maximum principle.Current support: CNRS; partial support; CEE contract GADGET # SC1-0105-C.