Limit laws for coverage in backbone-sensor networks

We study coverage in sensor networks having two types of nodes, namely, sensor nodes and backbone nodes. Each sensor is capable of transmitting information over relatively small distances. The backbone nodes collect information from the sensors. This information is processed and communicated over an ad hoc network formed by the backbone nodes, which are capable of transmitting over much larger distances. We consider two models of deployment for the sensor and backbone nodes. One is a Poisson–Poisson cluster model and the other a dependently thinned Poisson point process. We deduce limit laws for functionals of vacancy in both models using properties of association for random measures.     

Scenario reduction in stochastic programming

 Given a convex stochastic programming problem with a discrete initial probability distribution, the problem of optimal scenario reduction is stated as follows: Determine a scenario subset of prescribed cardinality and a probability measure based on this set that is the closest to the initial distribution in terms of a natural (or canonical) probability metric. Arguments from stability analysis indicate that Fortet-Mourier type probability metrics may serve as such canonical metrics. Efficient algorithms are developed that determine optimal reduced measures approximately. Numerical experience is reported for reductions of electrical load scenario trees for power management under uncertainty. For instance, it turns out that after 50% reduction of the scenario tree the optimal reduced tree still has about 90% relative accuracy. Received: July 2000 / Accepted: May 2002 Published online: February 14, 2003 Key words. stochastic programming – quantitative stability – Fortet-Mourier metrics – scenario reduction – transportation problem – electrical load scenario tree Mathematics Subject Classification (1991): 90C15, 90C31     

Perturbations of elliptic operators on high codimension subsets and the extension theory on an indefinite metric space

The spectral aspect of the problem of perturbations supported on thin sets of codimension θ≥2m in ℝⁿ is considered for elliptic operators of order m. The problem of realization of such perturbations is formulated as a problem of self-adjoint extension of a linear symmetric relation in a space with indefinite metric. It is shown how to construct such a relation for a given elliptic operator and a family of distributions. Its functional model is obtained in terms of Q-functions. Self-adjoint extensions and their resolvents are described. The theory developed is applied to quantum models of point interactions in high dimensions and high moments. Bibliography: 35 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 222, 1900, pp. 246–292.     

Estimation of Transit Origin–Destination Matrices from Passenger Counts Using a Frequency-Based Approach

This paper investigates the transit passenger origin–destination (O–D) estimation problem in congested transit networks where updated passenger counts and outdated O–D matrices are available. The bi-level programming approach is used for the transit passenger O–D estimation problem. The upper level minimizes the sum of error measurements in passenger counts and O–D matrices, and the lower level is a new frequency-based stochastic user equilibrium (SUE) assignment model that can determine simultaneously the passenger overload delays and passenger route choices in congested transit network together with the resultant transit line frequencies. The lower-level problem can be formulated as either a logit-type or probit-type SUE transit assignment problem. A heuristic solution algorithm is developed for solving the proposed bi-level programming model which is applicable to congested transit networks. Finally, a case study on a simplified transit network connecting Kowloon urban area and the Hong Kong International Airport is provided to illustrate the applications of the proposed bi-level programming model and solution algorithm. This revised version was published online in July 2006 with corrections to the Cover Date.     

Fast computation of the field of a vertical magnetic dipole above a layered medium

We consider the direct problem of aeroelectrosounding for a layered medium. The specific feature of this problem is that its solution is representable as a Bessel transform of a function ƒ of a certain type. We have developed and implemented a method for fast computation of the Bessel transform of such functions. The method relies on the approximation of ƒ by a linear combination of exponentials with prespecified exponents. The Bessel transform of the original function ƒ is computed analytically as the Bessel transform of the approximating linear combination. Numerical computations have been carried out. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 39–48, 2007.     

Determining the internal boundary of a region in the two-dimensional initial–boundary-value problem for the heat equation

The article investigates the reconstruction of the internal boundary of a two-dimensional region in the two-dimensional initial–boundary-value problem for the homogeneous heat equation. The initial values for the determination of the internal boundary are provided by a boundary condition of second kind on the external boundary and the solution of the initial–boundary-value problem at finitely many points inside the region. The inverse problem is reduced to solving a system of integral equations nonlinear in the function describing the sought boundary. An iterative numerical procedure is proposed involving linearization of integral equations.     

Construction of Solutions and L^1-error Estimates of Viscous Methods for Scalar Conservation Laws with Boundary

This paper is concerned with an initial boundary value problem for strictly convex conservation laws whose weak entropy solution is in the piecewise smooth solution class consisting of finitely many discontinuities. By the structure of the weak entropy solution of the corresponding initial value problem and the boundary entropy condition developed by Bardos-Leroux Nedelec, we give a construction method to the weak entropy solution of the initial boundary value problem. Compared with the initial value problem, the weak entropy solution of the initial boundary value problem includes the following new interaction type： an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary. According to the structure and some global estimates of the weak entropy solution, we derive the global L^1-error estimate for viscous methods to this initial boundary value problem by using the matching travelling wave solutions method. If the inviscid solution includes the interaction that an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary, or the inviscid solution includes some shock wave which is tangent to the boundary, then the error of the viscosity solution to the inviscid solution is bounded by O（ε^1/2） in L^1-norm; otherwise, as in the initial value problem, the L^1-error bound is O（ε｜ In ε｜）.     

Research on the target coverage algorithms for 3D curved surface

To solve the target covering problems in three-dimensional space, putting forward a deployment strategies of the target points innovatively, and referencing to the differential evolution (DE) algorithm to optimize the location coordinates of the sensor nodes to realize coverage of all the target points in 3-D surface with minimal sensor nodes. Firstly, building the three-dimensional perception model of sensor nodes, and putting forward to the blind area existing in the process of the sensor nodes sensing the target points in 3-D surface innovatively, then proving the feasibility of solving the target coverage problems in 3-D surface with DE algorithm theoretically, and reflecting the fault tolerance of the algorithm.     

Convergence and computation of simultaneous rational quadrature formulas

We discuss the convergence and numerical evaluation of simultaneous quadrature formulas which are exact for rational functions. The problem consists in integrating a single function with respect to different measures using a common set of quadrature nodes. Given a multi-index n, the nodes of the integration rule are the zeros of the multi-orthogonal Hermite–Padé polynomial with respect to (S, α, n), where S is a collection of measures, and α is a polynomial which modifies the measures in S. The theory is based on the connection between Gauss-type simultaneous quadrature formulas of rational type and multipoint Hermite–Padé approximation. The numerical treatment relies on the technique of modifying the integrand by means of a change of variable when it has real poles close to the integration interval. The output of some tests show the power of this approach in comparison with other ones in use.     

Conditioning of convex piecewise linear stochastic programs

 In this paper we consider stochastic programming problems where the objective function is given as an expected value of a convex piecewise linear random function. With an optimal solution of such a problem we associate a condition number which characterizes well or ill conditioning of the problem. Using theory of Large Deviations we show that the sample size needed to calculate the optimal solution of such problem with a given probability is approximately proportional to the condition number. Received: May 2000 / Accepted: May 2002-07-16 Published online: September 5, 2002 RID="★" The research of this author was supported, in part, by grant DMS-0073770 from the National Science Foundation Key Words. stochastic programming – Monte Carlo simulation – large deviations theory – ill-conditioned problems     

Numerical method for coupling the macro and meso scales in stochastic chemical kinetics

A numerical method is developed for simulation of stochastic chemical reactions. The system is modeled by the Fokker–Planck equation for the probability density of the molecular state. The dimension of the domain of the equation is reduced by assuming that most of the molecular species have a normal distribution with a small variance. The numerical approximation preserves properties of the analytical solution such as non-negativity and constant total probability. The method is applied to a nine dimensional problem modelling an oscillating molecular clock. The oscillations stop at a fixed point with a macroscopic model but they continue with our two dimensional, mixed macroscopic and mesoscopic model. Dedicated to the memory of Germund Dahlquist (1925–2005). AMS subject classification (2000)  65M20, 65M60     

Intra-domain traffic engineering with shortest path routing protocols

Throughout the last decade, extensive deployment of popular intra-domain routing protocols such as open shortest path first and intermediate system–intermediate system, has drawn an ever increasing attention to Internet traffic engineering. This paper reviews optimization techniques that have been deployed for managing intra-domain routing in networks operated with shortest path routing protocols, and the state-of-the-art research that has been carried out in this direction.     

Smoothing algorithms for state–space models

Two-filter smoothing is a principled approach for performing optimal smoothing in non-linear non-Gaussian state–space models where the smoothing distributions are computed through the combination of ‘forward’ and ‘backward’ time filters. The ‘forward’ filter is the standard Bayesian filter but the ‘backward’ filter, generally referred to as the backward information filter, is not a probability measure on the space of the hidden Markov process. In cases where the backward information filter can be computed in closed form, this technical point is not important. However, for general state–space models where there is no closed form expression, this prohibits the use of flexible numerical techniques such as Sequential Monte Carlo (SMC) to approximate the two-filter smoothing formula. We propose here a generalised two-filter smoothing formula which only requires approximating probability distributions and applies to any state–space model, removing the need to make restrictive assumptions used in previous approaches to this problem. SMC algorithms are developed to implement this generalised recursion and we illustrate their performance on various problems.     

Mathematical model on the transmission of worms in wireless sensor network

Wireless sensor networks (WSNs) have received extensive attention due to their great potential in civil and military applications. The sensor nodes have limited power and radio communication capabilities. As sensor nodes are resource constrained, they generally have weak defense capabilities and are attractive targets for software attacks. Cyber attack by worm presents one of the most dangerous threats to the security and integrity of the computer and WSN. In this paper, we study the attacking behavior of possible worms in WSN. Using compartmental epidemic model, we propose susceptible – exposed – infectious – recovered – susceptible with a vaccination compartment (SEIRS-V) to describe the dynamics of worm propagation with respect to time in WSN. The proposed model captures both the spatial and temporal dynamics of worms spread process. Reproduction number, equilibria, and their stability are also found. If reproduction number is less than one, the infected fraction of the sensor nodes disappears and if the reproduction number is greater than one, the infected fraction persists and the feasible region is asymptotically stable region for the endemic equilibrium state. Numerical methods are employed to solve and simulate the systems of equations developed and also to validate our model. A critical analysis of vaccination class with respect to susceptible class and infectious class has been made for a positive impact of increasing security measures on worm propagation in WSN.     

Equal-stressed reinforcement of metal-composite plates with fibers of constant cross section in steady-state creep

The problem on equal-stressed reinforcement of metal-composite plates with fibers of constant cross section, loaded in their plane and operating under the conditions of steady-state creep, is formulated. A qualitative analysis of the corresponding system of resolving equations and boundary conditions is performed. An important case of the problem is considered, where both the reinforcing fibers and the matrix are equally stressed. A method for numerically solving this problem is developed. Particular analytical and approximate solutions are discussed, with the example of which changes in the reinforcement structure in relation to the stress level in the reinforcing fibers are clarified. It is shown that nonunique solutions to such problems can exist. __________ Translated from Mekhanika Kompozitnykh Materialov, Vol. 44, No. 1, pp. 11–34, January–February, 2008.     

Fast deterministic approximation for the multicommodity flow problem

In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ε ⁻² + logk) logn) 1-commodity minimum-cost flow computations, wherek is the number of commodities,n is the number of nodes, andε is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995) the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem. A preliminary version of this paper appeared inProceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, 1995, pp. 486–492.     

Dynamic knapsack sets and capacitated lot-sizing

 A dynamic knapsack set is a natural generalization of the 0-1 knapsack set with a continuous variable studied recently. For dynamic knapsack sets a large family of facet-defining inequalities, called dynamic knapsack inequalities, are derived by fixing variables to one and then lifting. Surprisingly such inequalities have the simultaneous lifting property, and for small instances provide a significant proportion of all the facet-defining inequalities. We then consider single-item capacitated lot-sizing problems, and propose the joint study of three related sets. The first models the discrete lot-sizing problem, the second the continuous lot-sizing problem with Wagner-Whitin costs, and the third the continuous lot-sizing problem with arbitrary costs. The first set that arises is precisely a dynamic knapsack set, the second an intersection of dynamic knapsack sets, and the unrestricted problem can be viewed as both a relaxation and a restriction of the second. It follows that the dynamic knapsack inequalities and their generalizations provide strong valid inequalities for all three sets. Some limited computation results are reported as an initial test of the effectiveness of these inequalities on capacitated lot-sizing problems. Received: March 28, 2001 / Accepted: November 9, 2001 Published online: September 27, 2002 RID="★" ID="★" Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union. Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium. Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium. Key words. knapsack sets – valid inequalities – simultaneous lifting – lot-sizing – Wagner-Whitin costs     

Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints

 Multidimensional optimization problems where the objective function and the constraints are multiextremal non-differentiable Lipschitz functions (with unknown Lipschitz constants) and the feasible region is a finite collection of robust nonconvex subregions are considered. Both the objective function and the constraints may be partially defined. To solve such problems an algorithm is proposed, that uses Peano space-filling curves and the index scheme to reduce the original problem to a H?lder one-dimensional one. Local tuning on the behaviour of the objective function and constraints is used during the work of the global optimization procedure in order to accelerate the search. The method neither uses penalty coefficients nor additional variables. Convergence conditions are established. Numerical experiments confirm the good performance of the technique. Received: April 2002 / Accepted: December 2002 Published online: March 21, 2003 RID="⋆" ID="⋆" This research was supported by the following grants: FIRB RBNE01WBBB, FIRB RBAU01JYPN, and RFBR 01–01–00587. Key Words. global optimization – multiextremal constraints – local tuning – index approach     

Exponential growth of positive initial-energy solutions of a system of nonlinear viscoelastic wave equations with damping and source terms

This work is concerned with a system of nonlinear viscoelastic wave equations with nonlinear damping and source terms acting in both equations. We will prove that the energy associated to the system is unbounded. In fact, it will be proved that the energy will grow up as an exponential function as time goes to infinity, provided that the initial data are large enough. The key ingredient in the proof is a method used in Vitillaro (Arch Ration Mech Anal 149:155–182, 1999) and developed in Said-Houari (Diff Integr Equ 23(1–2):79–92, 2010) for a system of wave equations, with necessary modification imposed by the nature of our problem.     

The Multivariate Integer Chebyshev Problem

The multivariate integer Chebyshev problem is to find polynomials with integer coefficients that minimize the supremum norm over a compact set in ℂ ^d . We study this problem on general sets but devote special attention to product sets such as cube and polydisk. We also establish a multivariate analog of the Hilbert–Fekete upper bound for the integer Chebyshev constant, which depends on the dimension of space. In the case of single-variable polynomials in the complex plane, our estimate coincides with the Hilbert–Fekete result.