Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Networks

IEEE 802.16 standards for Wireless Metropolitan Area Networks (WMANs) include a mesh mode of operation for improving the coverage and throughput of the network. In this paper, we consider the problem of routing and centralized scheduling for such networks. We first fix the routing, which reduces the network to a tree. We then present a finite horizon dynamic programming framework. Using it we obtain various scheduling algorithms depending upon the cost function. Next we consider simpler suboptimal algorithms and compare their performances.

Stochastic Approximation Algorithms for Constrained Optimization via Simulation

We develop four algorithms for simulation-based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian, while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique, while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving an open Jackson network. The Newton-based SF algorithm is seen to show the best overall performance.

A Numerical Scheme for Three-Dimensional Front Propagation and Control of Jordan Mode

As an example of a front propagation, we study the propagation of a three-dimensional nonlinear wavefront into a polytropic gas in a uniform state and at rest. The successive positions and geometry of the wavefront are obtained by solving the conservation form of equations of a weakly nonlinear ray theory. The proposed set of equations forms a weakly hyperbolic system of seven conservation laws with an additional vector constraint, each of whose components is a divergence-free condition. This constraint is an involution for the system of conservation laws, and it is termed a geometric solenoidal constraint. The analysis of a Cauchy problem for the linearized system shows that when this constraint is satisfied initially, the solution does not exhibit any Jordan mode. For the numerical simulation of the conservation laws we employ a high resolution central scheme. The second order accuracy of the scheme is achieved by using MUSCL-type reconstructions and Runge-Kutta time discretizations. A constrained transport-type technique is used to enforce the geometric solenoidal constraint. The results of several numerical experiments are presented, which confirm the efficiency and robustness of the proposed numerical method and the control of the Jordan mode.

The Lovasz θ function, SVMs and finding large dense subgraphs

The Lovasz θ function of a graph, is a fundamental tool in combinatorial optimization and approximation algorithms. Computing θ involves solving a SDP and is extremely expensive even for moderately sized graphs. In this paper we establish that the Lovasz θ function is equivalent to a kernel learning problem related to one class SVM. This interesting connection opens up many opportunities bridging graph theoretic algorithms and machine learning. We show that there exist graphs, which we call SVM−θ graphs, on which the Lovasz θ function can be approximated well by a one-class SVM. This leads to a novel use of SVM techniques to solve algorithmic problems in large graphs e.g. identifying a planted clique of size Θ(n√) in a random graph G(n,12). A classic approach for this problem involves computing the θ function, however it is not scalable due to SDP computation. We show that the random graph with a planted clique is an example of SVM−θ graph, and as a consequence a SVM based approach easily identifies the clique in large graphs and is competitive with the state-of-the-art. Further, we introduce the notion of a ''common orthogonal labeling'' which extends the notion of a ''orthogonal labelling of a single graph (used in defining the θ function) to multiple graphs. The problem of finding the optimal common orthogonal labelling is cast as a Multiple Kernel Learning problem and is used to identify a large common dense region in multiple graphs. The proposed algorithm achieves an order of magnitude scalability compared to the state of the art.

Einstein Relation in n-Channel Inversion Layers of Nonlinear Optical, Optoelectronic and Related Materials: Simplified Theory, Relative Comparison and Suggestion for an Experimental Determination

In this paper, we study the Einstein relation for the diffusivity to mobility ratio (DMR) in n-channel inversion layers of non-linear optical materials on the basis of a newly formulated electron dispersion relation by considering their special properties within the frame work of k.p formalism. The results for the n-channel inversion layers of III-V, ternary and quaternary materials form a special case of our generalized analysis. The DMR for n-channel inversion layers of II-VI, IV-VI and stressed materials has been investigated by formulating the respective 2D electron dispersion laws. It has been found, taking n-channel inversion layers of CdGeAs2, Cd(3)AS(2), InAs, InSb, Hg1-xCdxTe, In1-xGaxAsyP1-y lattice matched to InP, CdS, PbTe, PbSnTe, Pb1-xSnxSe and stressed InSb as examples, that the DMR increases with the increasing surface electric field with different numerical values and the nature of the variations are totally band structure dependent. The well-known expression of the DMR for wide gap materials has been obtained as a special case under certain limiting conditions and this compatibility is an indirect test for our generalized formalism. Besides, an experimental method of determining the 2D DMR for n-channel inversion layers having arbitrary dispersion laws has been suggested.

Structural characteristics of a giant tropical liana and its mode of canopy spread in an alien environment

To circumvent the practical difficulties in research on tropical rainforest lianas in their natural habitat due to prevailing weather conditions, dense camouflaging vegetation and problems in transporting equipment for experimental investigations, Entada pursaetha DC (syn. Entada scandens Benth., Leguminosae) was grown inside a research campus in a dry subtropical environment. A solitary genet has attained a gigantic size in 17 years, infesting crowns of semi-evergreen trees growing in an area roughly equivalent to 1.6 ha. It has used aerially formed, cable-like stolons for navigating and spreading its canopy across tree gaps. Some of its parts which had remained unseen in its natural habitat due to dense vegetation are described. The attained size of this liana in a climatically different environment raises the question as to why it is restricted to evergreen rainforests. Some research problems for which this liana will be useful are pointed out.

Deformation and stability regression models for soil nail walls

Lateral displacement and global stability are the two main stability criteria for soil nail walls. Conventional design methods do not adequately address the deformation behaviour of soil nail walls, owing to the complexity involved in handling a large number of influencing factors. Consequently, limited methods of deformation estimates based on empirical relationships and in situ performance monitoring are available in the literature. It is therefore desirable that numerical techniques and statistical methods are used in order to gain a better insight into the deformation behaviour of soil nail walls. In the present study numerical experiments are conducted using a 2 4 factorial design method. Based on analysis of the maximum lateral deformation and factor-of-safety observations from the numerical experiments, regression models for maximum lateral deformation and factor-of-safety prediction are developed and checked for adequacy. Selection of suitable design factors for the 2 4 factorial design of numerical experiments enabled the use of the proposed regression models over a practical range of soil nail wall heights and in situ soil variability. It is evident from the model adequacy analyses and illustrative example that the proposed regression models provided a reasonably good estimate of the lateral deformation and global factor of safety of the soil nail walls.

Multicarrier analysis of magnetotransport data at low and high electric fields

We present some results on multicarrier analysis of magnetotransport data, Both synthetic as well as data from narrow gap Hg0.8Cd0.2Te samples are used to demonstrate applicability of various algorithms vs. nonlinear least square fitting, Quantitative Mobility Spectrum Analysis (QMSA) and Maximum Entropy Mobility Spectrum Analysis (MEMSA). Comments are made from our experience oil these algorithms, and, on the inversion procedure from experimental R/sigma-B to S-mu specifically with least square fitting as an example. Amongst the conclusions drawn are: (i) Experimentally measured resistivity (R-xx, R-xy) should also be used instead of just the inverted conductivity (sigma(xx), sigma(xy)) to fit data to semiclassical expressions for better fits especially at higher B. (ii) High magnetic field is necessary to extract low mobility carrier parameters. (iii) Provided the error in data is not large, better estimates to carrier parameters of remaining carrier species can be obtained at any stage by subtracting highest mobility carrier contribution to sigma from the experimental data and fitting with the remaining carriers. (iv)Even in presence of high electric field, an approximate multicarrier expression can be used to guess the carrier mobilities and their variations before solving the full Boltzmann equation.

The alpha method for solving differential algebraic inequality (DAI) systems

This paper describes an algorithm for ``direct numerical integration'' of the initial value Differential-Algebraic Inequalities (DAI) in a time stepping fashion using a sequential quadratic programming (SQP) method solver for detecting and satisfying active path constraints at each time step. The activation of a path constraint generally increases the condition number of the active discretized differential algebraic equation's (DAE) Jacobian and this difficulty is addressed by a regularization property of the alpha method. The algorithm is locally stable when index 1 and index 2 active path constraints and bounds are active. Subject to available regularization it is seen to be stable for active index 3 active path constraints in the numerical examples. For the high index active path constraints, the algorithm uses a user-selectable parameter to perturb the smaller singular values of the Jacobian with a view to reducing the condition number so that the simulation can proceed. The algorithm can be used as a relatively cheaper estimation tool for trajectory and control planning and in the context of model predictive control solutions. It can also be used to generate initial guess values of optimization variables used as input to inequality path constrained dynamic optimization problems. The method is illustrated with examples from space vehicle trajectory and robot path planning.

Selective dissemination of XML documents based on genetically learned user model and Support Vector Machines

Extensible Markup Language ( XML) has emerged as a medium for interoperability over the Internet. As the number of documents published in the form of XML is increasing, there is a need for selective dissemination of XML documents based on user interests. In the proposed technique, a combination of Adaptive Genetic Algorithms and multi class Support Vector Machine ( SVM) is used to learn a user model. Based on the feedback from the users, the system automatically adapts to the user's preference and interests. The user model and a similarity metric are used for selective dissemination of a continuous stream of XML documents. Experimental evaluations performed over a wide range of XML documents, indicate that the proposed approach significantly improves the performance of the selective dissemination task, with respect to accuracy and efficiency.

Selective dissemination of XML documents based on genetically learned user model and Support Vector Machines

Extensible Markup Language ( XML) has emerged as a medium for interoperability over the Internet. As the number of documents published in the form of XML is increasing, there is a need for selective dissemination of XML documents based on user interests. In the proposed technique, a combination of Adaptive Genetic Algorithms and multi class Support Vector Machine ( SVM) is used to learn a user model. Based on the feedback from the users, the system automatically adapts to the user's preference and interests. The user model and a similarity metric are used for selective dissemination of a continuous stream of XML documents. Experimental evaluations performed over a wide range of XML documents, indicate that the proposed approach significantly improves the performance of the selective dissemination task, with respect to accuracy and efficiency.

Minimizing total weighted tardiness on a batch-processing machine with non-agreeable release times and due dates

This study considers the scheduling problem observed in the burn-in operation of semiconductor final testing, where jobs are associated with release times, due dates, processing times, sizes, and non-agreeable release times and due dates. The burn-in oven is modeled as a batch-processing machine which can process a batch of several jobs as long as the total sizes of the jobs do not exceed the machine capacity and the processing time of a batch is equal to the longest time among all the jobs in the batch. Due to the importance of on-time delivery in semiconductor manufacturing, the objective measure of this problem is to minimize total weighted tardiness. We have formulated the scheduling problem into an integer linear programming model and empirically show its computational intractability. Due to the computational intractability, we propose a few simple greedy heuristic algorithms and meta-heuristic algorithm, simulated annealing (SA). A series of computational experiments are conducted to evaluate the performance of the proposed heuristic algorithms in comparison with exact solution on various small-size problem instances and in comparison with estimated optimal solution on various real-life large size problem instances. The computational results show that the SA algorithm, with initial solution obtained using our own proposed greedy heuristic algorithm, consistently finds a robust solution in a reasonable amount of computation time.

SPSA algorithms with measurement reuse

Four algorithms, all variants of Simultaneous Perturbation Stochastic Approximation (SPSA), are proposed. The original one-measurement SPSA uses an estimate of the gradient of objective function L containing an additional bias term not seen in two-measurement SPSA. As a result, the asymptotic covariance matrix of the iterate convergence process has a bias term. We propose a one-measurement algorithm that eliminates this bias, and has asymptotic convergence properties making for easier comparison with the two-measurement SPSA. The algorithm, under certain conditions, outperforms both forms of SPSA with the only overhead being the storage of a single measurement. We also propose a similar algorithm that uses perturbations obtained from normalized Hadamard matrices. The convergence w.p. 1 of both algorithms is established. We extend measurement reuse to design two second-order SPSA algorithms and sketch the convergence analysis. Finally, we present simulation results on an illustrative minimization problem.

Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.

An ensemble of B-DNA dinucleotide geometries lead to characteristic nucleosomal DNA structure and provide plasticity required for gene expression

Background: A nucleosome is the fundamental repeating unit of the eukaryotic chromosome. It has been shown that the positioning of a majority of nucleosomes is primarily controlled by factors other than the intrinsic preference of the DNA sequence. One of the key questions in this context is the role, if any, that can be played by the variability of nucleosomal DNA structure. Results: In this study, we have addressed this question by analysing the variability at the dinucleotide and trinucleotide as well as longer length scales in a dataset of nucleosome X-ray crystal structures. We observe that the nucleosome structure displays remarkable local level structural versatility within the B-DNA family. The nucleosomal DNA also incorporates a large number of kinks. Conclusions: Based on our results, we propose that the local and global level versatility of B-DNA structure may be a significant factor modulating the formation of nucleosomes in the vicinity of high-plasticity genes, and in varying the probability of binding by regulatory proteins. Hence, these factors should be incorporated in the prediction algorithms and there may not be a unique `template' for predicting putative nucleosome sequences. In addition, the multimodal distribution of dinucleotide parameters for some steps and the presence of a large number of kinks in the nucleosomal DNA structure indicate that the linear elastic model, used by several algorithms to predict the energetic cost of nucleosome formation, may lead to incorrect results.