Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

Bayesian Monte Carlo estimation for profile hidden Markov models

Hidden Markov models are used as tools for pattern recognition in a number of areas, ranging from speech processing to biological sequence analysis. Profile hidden Markov models represent a class of so-called “left–right” models that have an architecture that is specifically relevant to classification of proteins into structural families based on their amino acid sequences. Standard learning methods for such models employ a variety of heuristics applied to the expectation-maximization implementation of the maximum likelihood estimation procedure in order to find the global maximum of the likelihood function. Here, we compare maximum likelihood estimation to fully Bayesian estimation of parameters for profile hidden Markov models with a small number of parameters. We find that, relative to maximum likelihood methods, Bayesian methods assign higher scores to data sequences that are distantly related to the pattern consensus, show better performance in classifying these sequences correctly, and continue to perform robustly with regard to misspecification of the number of model parameters. Though our study is limited in scope, we expect our results to remain relevant for models with a large number of parameters and other types of left–right hidden Markov models.     

COMPLEXITY,MULTIRESOLUTION, NON-STATIONARITY AND ENTROPIC SCALING: TEEN BIRTH THERMODYNAMICS

This paper presents a statistical methodology for analyzing a complex phenomenon in which deterministic and scaling components are superimposed. Our approach is based on the wavelet multiresolution analysis combined with the scaling analysis of the entropy of a time series. The wavelet multiresolution analysis decomposes the signal in a scale-by-scale manner. The scale-by-scale decomposition generates smooth and detail curves that are evaluated and studied. A wavelet-based smoothing filtering is used to estimate the daily birth rate and conception rate during the year. The scaling analysis is based on the Diffusion Entropy Analysis (DEA). The joint use of the DEA and the wavelet multiresolution analysis allows: 1) the separation of the deterministic and, therefore, non-scaling component from the scaling component of the signal; 2) the determination of the stochastic information characterizing the teen birth phenomenon at each time scale. The daily data cover the number of births phenomenon at each time scale. The daily data cover the number of births to teens in Texas during the period 1964-1999.     

Semi-parametric multivariate modelling when the marginals are the same

A model is developed for multivariate distributions which have nearly the same marginals, up to shift and scale. This model, based on “interpolation” of characteristic functions, gives a new notion of “correlation”. It allows straightforward nonparametric estimation of the common marginal distribution, which avoids the “curse of dimensionality” present when nonparametically estimating the full multivariate distribution. The method is illustrated with environmental monitoring network data, where multivariate modelling with common marginals is often appropriate.     

Maximum thick paths in static and dynamic environments

We consider the problem of finding a large number of disjoint paths for unit disks moving amidst static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding “no-fly zones” and predicted weather hazards. For the static case we give efficient exact algorithms, based on adapting the “continuous uppermost path” paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem.Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. Deciding the existence of just one path, even for a 0-radius disk, moving with bounded speed is NP-hard, as shown by Canny and Reif [J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in: Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49–60]. Moreover, we observe that determining the existence of a given number of paths is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying “dual” approximations, compromising on the radius of the disks and on the maximum speed of motion.Our main result is a pseudopolynomial-time dual-approximation algorithm. If K unit disks, each moving with speed at most 1, can be routed through an environment, our algorithm finds (at least) K paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1.     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

AIC, Overfitting Principles, and the Boundedness of Moments of Inverse Matrices for Vector Autotregressions and Related Models

In his somewhat informal derivation, Akaike (in “Proceedings of the 2nd International Symposium Information Theory” (C. B. Petrov and F. Csaki, Eds.), pp. 610–624, Academici Kiado, Budapest, 1973) obtained AIC's parameter-count adjustment to the log-likelihood as a bias correction: it yields an asymptotically unbiased estimate of the quantity that measures the average fit of the estimated model to an independent replicate of the data used for estimation. We present the first mathematically complete derivation of an analogous property of AIC for comparing vector autoregressions fit to weakly stationary series. As a preparatory result, we derive a very general “overfitting principle,” first formulated in a more limited context in Findley (Ann. Inst. Statist. Math.43, 509–514, 1991), asserting that a natural measure of an estimated model's overfit due to parameter estimation is equal, asymptotically, to a measure of its accuracy loss with independent replicates. A formal principle of parsimony for fitted models is obtained from this, which for nested models, covers the situation in which all models considered are misspecified. To prove these results, we establish a set of general conditions under which, for each τ1, the absolute τth moments of the entries of the inverse matrices associated with least squares estimation are bounded for sufficiently large sample sizes.     

The estimation of the bispectral density function and the detection of periodicities in a signal

In a recent paper Subba Rao and Gabr (J. Time Ser. Anal. (1987), in press) considered the estimation of the spectrum and the inverse spectrum based on the method by Pisarenko (Geophys. J. Roy. Astronom. Soc. 28 (1972), 511–531). The asymptotic properties of these estimates were studied using the properties of Wishart matrices. In this paper we show how the method can be extended to the estimation of the bispectral density function, an important tool in the study of non-Gaussian time series. All these methods of estimation are illustrated with simulated examples. In the illustrations considered, the emphasis is on the detection of periodicities in the “signal” (possibly in the presence of noise). We also considered an example based on real data. These data arise in the study of the earth's magnetic reversals and the detection of periodicities.     

Simulation and Analysis of a New Mobility Model for Mobile Communication Networks

The traffic generation models, which describe how the clients use the network services, as well as the mobility models, which describe how clients move within the service area covered by the network, are essential tools for QoS analysis in these environments. In this paper we present the simulation of a new mobility model implemented for the analysis of QoS parameters of a mobile network, such as channel occupation time, handoff and new call blocking probabilities.     

基于方向多尺度变换和统计建模的纹理分类方法

纹理是图像分析和识别中经常使用的关键特征, 而小波变换则是图像纹理表示和分类中的常用工具. 然而, 基于小波变换的纹理分类方法常常忽略了小波低频子带信息, 并且无法提取图像纹理的块状奇异信息. 本文提出小波子带系数的局部能量直方图建模方法、轮廓波特征的Poisson 混合模型建模方法和基于轮廓波子带系数聚类的特征提取方法, 并将其应用于图像纹理分类上. 基于局部能量直方图的纹理分类方法解决了小波低频子带的建模难题, 基于Poisson 混合模型的纹理分类方法则首次将Poisson 混合模型用于轮廓子带特征的建模, 而基于轮廓波域聚类的纹理分类方法是一种快速的分类方法. 实验结果显示, 本文所提出的三类方法都超过了当前典型的纹理分类方法.     

The on–off network traffic model under intermediate scaling

The result provided in this paper helps complete a unified picture of the scaling behavior in heavy-tailed stochastic models for transmission of packet traffic on high-speed communication links. Popular models include infinite source Poisson models, models based on aggregated renewal sequences, and models built from aggregated on–off sources. The versions of these models with finite variance transmission rate share the following pattern: if the sources connect at a fast rate over time the cumulative statistical fluctuations are fractional Brownian motion, if the connection rate is slow the traffic fluctuations are described by a stable Lévy motion, while the limiting fluctuations for the intermediate scaling regime are given by fractional Poisson motion. In this paper, we prove an invariance principle for the normalized cumulative workload of a network with m on–off sources and time rescaled by a factor a. When both the number of sources m and the time scale a tend to infinity with a relative growth given by the so-called ’intermediate connection rate’ condition, the limit process is the fractional Poisson motion. The proof is based on a coupling between the on–off model and the renewal type model.     

Numerical comparison of nonlinear subgridscale models via adaptive mesh refinement

In this paper, we provide a method of evaluating the efficacy of nonlinear subgridscale models for use in the large eddy simulation of incompressible viscous flow problems. We compare subgridscale “artificial” viscosity models using a posteriori error estimation and adaptive mesh refinement. Specifically, we compare α-Laplacian based subgridscale models and discuss the benefits and limitations of different values of α for some standard benchmark problems for the Navier–Stokes equations.     

Wavelet Approximation of Periodic Functions

We investigate expansions of periodic functions with respect to wavelet bases. Direct and inverse theorems for wavelet approximation in C and L_p norms are proved. For the functions possessing local regularity we study the rate of pointwise convergence of wavelet Fourier series. We also define and investigate the “discreet wavelet Fourier transform” (DWFT) for periodic wavelets generated by a compactly supported scaling function. The DWFT has one important advantage for numerical problems compared with the corresponding wavelet Fourier coefficients: while fast computational algorithms for wavelet Fourier coefficients are recursive, DWFTs can be computed by explicit formulas without any recursion and the computation is fast enough.     

Nonlinear analysis of elastic thin-walled shell structures

Theoretical principles, methodology and algorithms presented herein are to analyze and design the elastic thin-walled engineering structures and components, with emphasis on the important nonlinear behavior. The methodology of the consequent analysis of single-parametric nonlinear problems is applied to structural syntheses. The numerical algorithm for this analysis is based on the parameter continuation methods and the “control parameter subspace changing”. The effectiveness of the proposed approach is illustrated through several examples in thin-walled structures.     

Scaling laws and fractality in the framework of a phenomenological approach

Phenomenological Universality (PUN) represents a new tool for the classification and interpretation of different non-linear phenomenologies in the context of cross-disciplinary research. Also, they can act as a “magnifying glass” to finetune the analysis and quantify the difference among similarly looking datasets. In particular, the class U2 is of special relevance since it includes, as subcases, most of the commonly used growth models proposed to date. In this contribution we consider two applications of special interest in two subfields of Elasto-dynamics, i.e. Fast- and Slow-Dynamics, respectively. The results suggest that new equations should be adopted for the fitting of the experimental results and that fractal-dimensioned variables should be used to recover the scaling invariance, which is invariably lost due to non-linearity.     

Several sufficient conditions of solvability for a nonlinear higher-order three-point boundary value problem with all derivatives

In this paper, firstly, some errors in the proof of our paper “Several sufficient conditions of solvability for a nonlinear higher-order three-point boundary value problem on time scales, Appl. Math. Comput. 190 (2007) 566–575” are pointed, and we make the corresponding correction when T=R. Then, the more general problem with all derivatives is considered. Under certain growth conditions on the nonlinearity, several sufficient conditions for the existence and uniqueness of nontrivial solution are obtained by using Leray–Schauder nonlinear alternative and Banach fixed point theorem.     

Nonlinearity effects in multidimensional scaling

When multidimensional scaling of n cases is derived from dissimilarities that are functions of p basic continuous variables, the question arises of how to relate the values of the variables to the configuration of n points. We provide a methodology based on nonlinear biplots that expresses nonlinearity in two ways: (i) each variable is represented by a nonlinear trajectory and (ii) each trajectory is calibrated by an irregular scale. Methods for computing, calibrating and interpreting these trajectories are given and exemplified. Not only are the tools of immediate practical utility but the methodology established assists in a critical appraisal of the consequences of using nonlinear measures in a variety of multidimensional scaling methods.     

CDS simulation and pattern formation of phase separation

Several properties of the generation and evolution of phase separating patterns for binary material studied by CDS model are proposed. The main conclusions are (1) for alloys spinodal decomposition, the conceptions of “macro-pattern” and “micropattern” are posed by “black-and- white graph” and “gray-scale graph” respectively. We find that though the four forms of map f that represent the self-evolution of order parameter in a cell (lattice) are similar to each other in “macro-pattern”, there are evident differences in their micro-pattern, e.g., some different fine netted structures in the black domain and the white domain are found by the micro-pattern, so that distinct mechanical and physical behaviors shall be obtained. (2) If the two constitutions of block copolymers are not symmetric (i.e. r ≠ 0.5), a pattern called “grain-strip cross pattern” is discovered, in the 0.43 <r <0.45.     

Small and Large Time Scale Analysis of a Network Traffic Model

Empirical studies of the internet and WAN traffic data have observed multifractal behavior at time scales below a few hundred milliseconds. There have been some attempts to model this phenomenon, but there is no model to connect the small time scale behavior with behavior observed at large time scales of bigger than a few hundred milliseconds. There have been separate analyses of models for high speed data transmissions, which show that appropriate approximations to large time scale behavior of cumulative traffic are either fractional Brownian motion or stable Lévy motion, depending on the input rates assumed. This paper tries to bridge this gap and develops and analyzes a model offering an explanation of both the small and large time scale behavior of a network traffic model based on the infinite source Poisson model. Previous studies of this model have usually assumed that transmission rates are constant and deterministic. We consider a nonconstant, multifractal, random transmission rate at the user level which results in cumulative traffic exhibiting multifractal behavior on small time scales and self-similar behavior on large time scales.     

Implication in fuzzy logic

Intermediate truth values and the order relation “as true as” are interpreted. The material implication A → B quantifies the degree by which “B is at least as true as A.” Axioms for the → operator lead to a representation of → by the pseudo-Lukasiewicz model. A canonical scale for the truth value of a fuzzy proposition is selected such that the → operator is the Lukasiewicz operator and the negation is the classical 1−. operator. The mathematical structure of some conjunction and disjunction operators related to → are derived.