Stochastic optimization for adaptive labor staffing in service systems

Service systems are labor intensive. Further, the workload tends to vary greatly with time. Adapting the staffing levels to the workloads in such systems is nontrivial due to a large number of parameters and operational variations, but crucial for business objectives such as minimal labor inventory. One of the central challenges is to optimize the staffing while maintaining system steady-state and compliance to aggregate SLA constraints. We formulate this problem as a parametrized constrained Markov process and propose a novel stochastic optimization algorithm for solving it. Our algorithm is a multi-timescale stochastic approximation scheme that incorporates a SPSA based algorithm for ‘primal descent' and couples it with a ‘dual ascent' scheme for the Lagrange multipliers. We validate this optimization scheme on five real-life service systems and compare it with a state-of-the-art optimization tool-kit OptQuest. Being two orders of magnitude faster than OptQuest, our scheme is particularly suitable for adaptive labor staffing. Also, we observe that it guarantees convergence and finds better solutions than OptQuest in many cases.

Dataflow analysis for data-race free programs

Memory models for shared-memory concurrent programming languages typically guarantee sequential consistency (SC) semantics for datarace-free (DRF) programs, while providing very weak or no guarantees for non-DRF programs. In effect programmers are expected to write only DRF programs, which are then executed with SC semantics. With this in mind, we propose a novel scalable solution for dataflow analysis of concurrent programs, which is proved to be sound for DRF programs with SC semantics. We use the synchronization structure of the program to propagate dataflow information among threads without requiring to consider all interleavings explicitly. Given a dataflow analysis that is sound for sequential programs and meets certain criteria, our technique automatically converts it to an analysis for concurrent programs.

A game theoretic approach for feature clustering and its application to feature selection

In this paper, we develop a game theoretic approach for clustering features in a learning problem. Feature clustering can serve as an important preprocessing step in many problems such as feature selection, dimensionality reduction, etc. In this approach, we view features as rational players of a coalitional game where they form coalitions (or clusters) among themselves in order to maximize their individual payoffs. We show how Nash Stable Partition (NSP), a well known concept in the coalitional game theory, provides a natural way of clustering features. Through this approach, one can obtain some desirable properties of the clusters by choosing appropriate payoff functions. For a small number of features, the NSP based clustering can be found by solving an integer linear program (ILP). However, for large number of features, the ILP based approach does not scale well and hence we propose a hierarchical approach. Interestingly, a key result that we prove on the equivalence between a k-size NSP of a coalitional game and minimum k-cut of an appropriately constructed graph comes in handy for large scale problems. In this paper, we use feature selection problem (in a classification setting) as a running example to illustrate our approach. We conduct experiments to illustrate the efficacy of our approach.

A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

A generic variant of NIST’s KAS2 key agreement protocol

We propose a generic three-pass key agreement protocol that is based on a certain kind of trapdoor one-way function family. When specialized to the RSA setting, the generic protocol yields the so-called KAS2 scheme that has recently been standardized by NIST. On the other hand, when specialized to the discrete log setting, we obtain a new protocol which we call DH2. An interesting feature of DH2 is that parties can use different groups (e.g., different elliptic curves). The generic protocol also has a hybrid implementation, where one party has an RSA key pair and the other party has a discrete log key pair. The security of KAS2 and DH2 is analyzed in an appropriate modification of the extended Canetti-Krawczyk security model.

On the dynamic contact angle in simulation of impinging droplets with sharp interface methods

Effects of dynamic contact angle models on the flow dynamics of an impinging droplet in sharp interface simulations are presented in this article. In the considered finite element scheme, the free surface is tracked using the arbitrary Lagrangian-Eulerian approach. The contact angle is incorporated into the model by replacing the curvature with the Laplace-Beltrami operator and integration by parts. Further, the Navier-slip with friction boundary condition is used to avoid stress singularities at the contact line. Our study demonstrates that the contact angle models have almost no influence on the flow dynamics of the non-wetting droplets. In computations of the wetting and partially wetting droplets, different contact angle models induce different flow dynamics, especially during recoiling. It is shown that a large value for the slip number has to be used in computations of the wetting and partially wetting droplets in order to reduce the effects of the contact angle models. Among all models, the equilibrium model is simple and easy to implement. Further, the equilibrium model also incorporates the contact angle hysteresis. Thus, the equilibrium contact angle model is preferred in sharp interface numerical schemes.

Micro-shock wave assisted bacterial transformation

A gene is a unit of heredity in a living organism. It normally resides on a stretch of DNA that codes for a type of protein or for an RNA chain that has a function in the organism. All living things depend on genes, as they specify all proteins and functional RNA chains. Genes hold the information to build and maintain an organism’s cells and pass genetic traits to offspring. The gene has to be transferred to bacteria or eukaryotic cells for basic and applied molecular biology studies. Bacteria can uptake exogenous genetic material by three ways: conjugation, transduction and transformation. Genetic material is naturally transferred to bacteria in case of conjugation and transferred through bacteriophage in transduction. Transformation is the acquisition of exogenous genetic material through cell wall. The ability of bacteria of being transformed is called competency and those bacteria which have competency are competent cells. Divalent Calcium ions can make the bacteria competent and a heat shock can cause the bacteria to uptake DNA. But the heat shock method cannot be used for all the bacteria. In electroporation, a brief electric shock with an electric field of 10-20kV/cmmakes pores in the cell wall, facilitates the DNA to enter into the bacteria. Microprecipitates, microinjection, liposomes, and biological vectors are also used to transfer polar molecules like DNA into host cells.

Farmers' vulnerability to climate variability in Dimapur district of Nagaland, India

Certain parts of the State of Nagaland situated in the northeastern region of India have been experiencing rainfall deficit over the past few years leading to severe drought-like conditions, which is likely to be aggravated under a climate change scenario. The state has already incurred considerable losses in the agricultural sector. Regional vulnerability assessments need to be carried out in order to help policy makers and planners formulate and implement effective drought management strategies. The present study uses an 'index-based approach' to quantify the climate variability-induced vulnerability of farmers in five villages of Dimapur district, Nagaland. Indicators, which are reflective of the exposure, sensitivity and adaptive capacity of the farmers to drought, were quantified on the basis of primary data generated through household surveys and participatory rural appraisal supplemented by secondary data in order to calculate a composite vulnerability index. The composite vulnerability index of village New Showba was found to be the least, while Zutovi, the highest. The overall results reveal that biophysical characteristics contribute the most to overall vulnerability. Some potential adaptation strategies were also identified based on observations and discussions with the villagers.

A regularized linear classifier for effective text classification

In document community support vector machines and naïve bayes classifier are known for their simplistic yet excellent performance. Normally the feature subsets used by these two approaches complement each other, however a little has been done to combine them. The essence of this paper is a linear classifier, very similar to these two. We propose a novel way of combining these two approaches, which synthesizes best of them into a hybrid model. We evaluate the proposed approach using 20ng dataset, and compare it with its counterparts. The efficacy of our results strongly corroborate the effectiveness of our approach.

Discriminative feature analysis and selection for document classification

Classification of a large document collection involves dealing with a huge feature space where each distinct word is a feature. In such an environment, classification is a costly task both in terms of running time and computing resources. Further it will not guarantee optimal results because it is likely to overfit by considering every feature for classification. In such a context, feature selection is inevitable. This work analyses the feature selection methods, explores the relations among them and attempts to find a minimal subset of features which are discriminative for document classification.

Feature selection for unsupervised learning

In this paper, we present a methodology for identifying best features from a large feature space. In high dimensional feature space nearest neighbor search is meaningless. In this feature space we see quality and performance issue with nearest neighbor search. Many data mining algorithms use nearest neighbor search. So instead of doing nearest neighbor search using all the features we need to select relevant features. We propose feature selection using Non-negative Matrix Factorization(NMF) and its application to nearest neighbor search. Recent clustering algorithm based on Locally Consistent Concept Factorization(LCCF) shows better quality of document clustering by using local geometrical and discriminating structure of the data. By using our feature selection method we have shown further improvement of performance in the clustering.

Hybrid online non-negative matrix factorization for clustering of documents

When document corpus is very large, we often need to reduce the number of features. But it is not possible to apply conventional Non-negative Matrix Factorization(NMF) on billion by million matrix as the matrix may not fit in memory. Here we present novel Online NMF algorithm. Using Online NMF, we reduced original high-dimensional space to low-dimensional space. Then we cluster all the documents in reduced dimension using k-means algorithm. We experimentally show that by processing small subsets of documents we will be able to achieve good performance. The method proposed outperforms existing algorithms.

Projecting low and extensive dimensional chaos from spatio-temporal dynamics

We review the spatio-temporal dynamical features of the Ananthakrishna model for the Portevin-Le Chatelier effect, a kind of plastic instability observed under constant strain rate deformation conditions. We then establish a qualitative correspondence between the spatio-temporal structures that evolve continuously in the instability domain and the nature of the irregularity of the scalar stress signal. Rest of the study is on quantifying the dynamical information contained in the stress signals about the spatio-temporal dynamics of the model. We show that at low applied strain rates, there is a one-to-one correspondence with the randomly nucleated isolated bursts of mobile dislocation density and the stress drops. We then show that the model equations are spatio-temporally chaotic by demonstrating the number of positive Lyapunov exponents and Lyapunov dimension scale with the system size at low and high strain rates. Using a modified algorithm for calculating correlation dimension density, we show that the stress-strain signals at low applied strain rates corresponding to spatially uncorrelated dislocation bands exhibit features of low dimensional chaos. This is made quantitative by demonstrating that the model equations can be approximately reduced to space independent model equations for the average dislocation densities, which is known to be low-dimensionally chaotic. However, the scaling regime for the correlation dimension shrinks with increasing applied strain rate due to increasing propensity for propagation of the dislocation bands. The stress signals in the partially propagating to fully propagating bands turn to have features of extensive chaos.

Data assimilation using ensemble transform Kalman filter (ETKF) in ROMS model for Indian Ocean

Study of Oceans dynamics and forecast is crucial as it influences the regional climate and other marine activities. Forecasting oceanographic states like sea surface currents, Sea surface temperature (SST) and mixed layer depth at different time scales is extremely important for these activities. These forecasts are generated by various ocean general circulation models (OGCM). One such model is the Regional Ocean Modelling System (ROMS). Though ROMS can simulate several features of ocean, it cannot reproduce the thermocline of the ocean properly. Solution to this problem is to incorporates data assimilation (DA) in the model. DA system using Ensemble Transform Kalman Filter (ETKF) has been developed for ROMS model to improve the accuracy of the model forecast. To assimilate data temperature and salinity from ARGO data has been used as observation. Assimilated temperature and salinity without localization shows oscillations compared to the model run without assimilation for India Ocean. Same was also found for u and v-velocity fields. With localization we found that the state variables are diverging within the localization scale.

Role of silica nanoparticles in conductivity enhancement of nanocomposite solid polymer electrolytes: (PEG(x) NaBr): ySiO(2)

Nanocomposite solid polymer electrolytes (NCSPEs) with conducting species other than Li ions are being investigated for solid-state battery applications. Pristine solid polymer electrolytes (SPEs) do not show ionic conductivity suitable for batteries. Addition of inert fillers to SPEs is known to enhance the ionic conductivity. In this paper, we present the role of silica nanoparticles in enhancing the ionic conductivity in NCSPEs with sodium as conducting species. Sodium bromide is complexed with the host polyethylene glycol polymer by solution cast method and silica nanoparticles (SiO2, average particle size 7 nm) are incorporated into the complex in small amounts. The composites are characterized by powder XRD and IR spectroscopy. Conductivity measurements are undertaken as a function of concentration of salt and also as a function of temperature using impedance spectroscopy. Addition of silica nanoparticles shows an enhancement in conductivity by 1-2 orders of magnitude. The results are discussed in terms of interaction of nanoparticles with the nonconducting anions.