Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

Newton-based stochastic optimization using q-Gaussian smoothed functional algorithms

We present the first q-Gaussian smoothed functional (SF) estimator of the Hessian and the first Newton-based stochastic optimization algorithm that estimates both the Hessian and the gradient of the objective function using q-Gaussian perturbations. Our algorithm requires only two system simulations (regardless of the parameter dimension) and estimates both the gradient and the Hessian at each update epoch using these. We also present a proof of convergence of the proposed algorithm. In a related recent work (Ghoshdastidar, Dukkipati, & Bhatnagar, 2014), we presented gradient SF algorithms based on the q-Gaussian perturbations. Our work extends prior work on SF algorithms by generalizing the class of perturbation distributions as most distributions reported in the literature for which SF algorithms are known to work turn out to be special cases of the q-Gaussian distribution. Besides studying the convergence properties of our algorithm analytically, we also show the results of numerical simulations on a model of a queuing network, that illustrate the significance of the proposed method. In particular, we observe that our algorithm performs better in most cases, over a wide range of q-values, in comparison to Newton SF algorithms with the Gaussian and Cauchy perturbations, as well as the gradient q-Gaussian SF algorithms. (C) 2014 Elsevier Ltd. All rights reserved.

Computational Study of the Formation of Short Centrosymmetric N-center dot center dot center dot S Supramolecular Synthon and Related Weak Interactions in Crystalline 1,2,4-Triazoles

A comprehensive analysis of the crystal packing and the energetic features of a series of four biologically active molecules belonging to the family of substituted 4-(benzylideneamino)-3-(4-fluoro-3-phenoxyphenyl)-1H-1,2,4-triazole-5-(4 H)-thione derivatives have been performed based on the molecular conformation and the supramolecular packing. This involves the formation of a short centrosymmetric R-2(2)(8) NH...S supramolecular synthon in the solid state, including the presence of CH...S, CH...O, CH...N, CH...F, CH...Cl, CF...FC, CCl...ClC, and CH...pi intermolecular interactions along with pp stacking to evaluate the role of noncovalent interactions in the crystal. The presence of such synthons has a substantial contribution toward the interaction energy (-18 to -20 kcal/mol) as obtained from the PIXEL calculation, wherein the Coulombic and polarization contribution are more significant than the dispersion contribution. The geometrical characteristics of such synthons favor short distance, and the population of related molecules having these geometries is rare as has been obtained from the Cambridge Structural Database (CSD). Furthermore, their interaction energies have been compared with those present in our molecules in the solid state. The topological characteristics of the NH...S supramolecular synthon, in addition to related weak interactions, CH...N, CH...Cl, CF...FC, and CCl...ClC, have been estimated using the quantum theory of atoms in molecules (QTAIM). In addition, an analysis of the Hirshfeld surface and associated fingerprint plots of these four molecules also have provided a platform for the evaluation of the contribution of different atom...atom contacts, which contribute toward the packing of the molecules in solids.

Cavitation in brittle metallic glasses - Effects of stress state and distributed weak zones

Experimental studies and atomistic simulations have shown that brittle metallic glasses fail by a cavitation mechanism whose origin has been traced to the presence of intrinsic atomic density fluctuations which give rise to weak zones with reduced yield strength. It has been shown recently through continuum analysis that the presence of these zones can lower the cavitation stress considerably under equibiaxial loading. The objective of the present work is to study the effect of the applied stress state on the cavitation behavior of such a heterogeneous plastic solid with distributed weak zones. To this end, 2D plane strain finite element simulations are performed by subjecting a unit cell containing a weak zone to different (biaxiality) stress ratios. The volume fraction and yield strength of the weak zone are varied over a wide range. The results show that unlike in a homogeneous plastic solid, the cavitation stress of the heterogeneous aggregate does not reduce appreciably as the stress ratio decreases from unity when the yield strength of the weak zone is low. It is found that a non-dimensional parameter characterizing the stress state prevailing in the weak zone and its yield properties uniquely control the cavitation stress. The nature of cavitation bifurcation may change from unstable bifurcation to the left at sufficiently low stress ratio to one involving snap cavitation at high stress ratio. (C) 2014 Elsevier Ltd. All rights reserved.

Dissociation Constants of Weak Acids from ab Initio Molecular Dynamics Using Metadynamics: Influence of the Inductive Effect and Hydrogen Bonding on pK(a) Values

The theoretical estimation of the dissociation constant, or pK(a), of weak acids continues to be a challenging field. Here, we show that ab initio CarParrinello molecular dynamics simulations in conjunction with metadynamics calculations of the free-energy profile of the dissociation reaction provide reasonable estimates of the pK(a) value. Water molecules, sufficient to complete the three hydration shells surrounding the acid molecule, were included explicitly in the computation procedure. The free-energy profiles exhibit two distinct minima corresponding to the dissociated and neutral states of the acid, and the difference in their values provides the estimate for pK(a). We show for a series of organic acids that CPMD simulations in conjunction with metadynamics can provide reasonable estimates of pK(a) values. The acids investigated were aliphatic carboxylic acids, chlorine-substituted carboxylic acids, cis- and trans-butenedioic acid, and the isomers of hydroxybenzoic acid. These systems were chosen to highlight that the procedure could correctly account for the influence of the inductive effect as well as hydrogen bonding on pK(a) values of weak organic acids. In both situations, the CPMD metadynamics procedure faithfully reproduces the experimentally observed trend and the magnitudes of the pK(a) values.

An iterative framework for sparse signal reconstruction algorithms

It has been shown that iterative re-weighted strategies will often improve the performance of many sparse reconstruction algorithms. However, these strategies are algorithm dependent and cannot be easily extended for an arbitrary sparse reconstruction algorithm. In this paper, we propose a general iterative framework and a novel algorithm which iteratively enhance the performance of any given arbitrary sparse reconstruction algorithm. We theoretically analyze the proposed method using restricted isometry property and derive sufficient conditions for convergence and performance improvement. We also evaluate the performance of the proposed method using numerical experiments with both synthetic and real-world data. (C) 2014 Elsevier B.V. All rights reserved.

Simultaneous Perturbation Newton Algorithms for Simulation Optimization

We present a new Hessian estimator based on the simultaneous perturbation procedure, that requires three system simulations regardless of the parameter dimension. We then present two Newton-based simulation optimization algorithms that incorporate this Hessian estimator. The two algorithms differ primarily in the manner in which the Hessian estimate is used. Both our algorithms do not compute the inverse Hessian explicitly, thereby saving on computational effort. While our first algorithm directly obtains the product of the inverse Hessian with the gradient of the objective, our second algorithm makes use of the Sherman-Morrison matrix inversion lemma to recursively estimate the inverse Hessian. We provide proofs of convergence for both our algorithms. Next, we consider an interesting application of our algorithms on a problem of road traffic control. Our algorithms are seen to exhibit better performance than two Newton algorithms from a recent prior work.

Secure Transmission in Cooperative Networks with Weak Eavesdroppers

In this letter, we propose a scheme to improve the secrecy rate of cooperative networks using Analog Network Coding (ANC). ANC mixes the signals in the air; the desired signal is then separated out, from the mixed signals, at the legitimate receiver using techniques like self interference subtraction and signal nulling, thereby achieving better secrecy rates. Assuming global channel state information, memoryless adversaries and the decode-and-forward strategy, we seek to maximize the average secrecy rate between the source and the destination, subject to an overall power budget. Then, exploiting the structure of the optimization problem, we compute its optimal solution. Finally, we use numerical evaluations to compare our scheme with the conventional approaches.

Energy Sharing for Multiple Sensor Nodes With Finite Buffers

We consider the problem of finding optimal energy sharing policies that maximize the network performance of a system comprising of multiple sensor nodes and a single energy harvesting (EH) source. Sensor nodes periodically sense the random field and generate data, which is stored in the corresponding data queues. The EH source harnesses energy from ambient energy sources and the generated energy is stored in an energy buffer. Sensor nodes receive energy for data transmission from the EH source. The EH source has to efficiently share the stored energy among the nodes to minimize the long-run average delay in data transmission. We formulate the problem of energy sharing between the nodes in the framework of average cost infinite-horizon Markov decision processes (MDPs). We develop efficient energy sharing algorithms, namely Q-learning algorithm with exploration mechanisms based on the epsilon-greedy method as well as upper confidence bound (UCB). We extend these algorithms by incorporating state and action space aggregation to tackle state-action space explosion in the MDP. We also develop a cross entropy based method that incorporates policy parameterization to find near optimal energy sharing policies. Through simulations, we show that our algorithms yield energy sharing policies that outperform the heuristic greedy method.

Spin-reorientation and weak ferromagnetism in antiferromagnetic TbMn0.5Fe0.5O3

Orthorhombic single crystals of TbMn0.5Fe0.5O3 are found to exhibit spin-reorientation, magnetization reversal, and weak ferromagnetism. Strong anisotropy effects are evident in the temperature dependent magnetization measurements along the three crystallographic axes a, b, and c. A broad magnetic transition is visible at T-N(Fe/Mn) = 286K due to paramagnetic to A(x)G(y)C(z) ordering. A sharp transition is observed at T-SR(Fe/Mn) = 28 K, which is pronounced along c axis in the form of a sharp jump in magnetization where the spins reorient to G(x)A(y)F(z) configuration. The negative magnetization observed below T-SR(Fe/Mn) along c axis is explained in terms of domain wall pinning. A component of weak ferromagnetism is observed in field-scans along c-axis but below 28 K. Field-induced steps-like transitions are observed in hysteresis measurement along b axis below 28 K. It is noted that no sign of Tb-order is discernible down to 2K. TbMn0.5Fe0.5O3 could be highlighted as a potential candidate to evaluate its magneto-dielectric effects across the magnetic transitions. (C) 2015 AIP Publishing LLC.

Timing Recovery Algorithms and Architectures for 2-D Magnetic Recording Systems

We investigate the problem of timing recovery for 2-D magnetic recording (TDMR) channels. We develop a timing error model for TDMR channel considering the phase and frequency offsets with noise. We propose a 2-D data-aided phase-locked loop (PLL) architecture for tracking variations in the position and movement of the read head in the down-track and cross-track directions and analyze the convergence of the algorithm under non-separable timing errors. We further develop a 2-D interpolation-based timing recovery scheme that works in conjunction with the 2-D PLL. We quantify the efficiency of our proposed algorithms by simulations over a 2-D magnetic recording channel with timing errors.

Reduced Look Ahead Orthogonal Matching Pursuit

Compressed Sensing (CS) is an elegant technique to acquire signals and reconstruct them efficiently by solving a system of under-determined linear equations. The excitement in this field stems from the fact that we can sample at a rate way below the Nyquist rate and still reconstruct the signal provided some conditions are met. Some of the popular greedy reconstruction algorithms are the Orthogonal Matching Pursuit (OMP), the Subspace Pursuit (SP) and the Look Ahead Orthogonal Matching Pursuit (LAOMP). The LAOMP performs better than the OMP. However, when compared to the SP and the OMP, the computational complexity of LAOMP is higher. We introduce a modified version of the LAOMP termed as Reduced Look Ahead Orthogonal Matching Pursuit (Reduced LAOMP). Reduced LAOMP uses prior information from the results of the OMP and the SP in the quest to speedup the look ahead strategy in the LAOMP. Monte Carlo simulations of this algorithm deliver promising results.

Multi-agent Reinforcement Learning for Traffic Signal Control

Optimal control of traffic lights at junctions or traffic signal control (TSC) is essential for reducing the average delay experienced by the road users amidst the rapid increase in the usage of vehicles. In this paper, we formulate the TSC problem as a discounted cost Markov decision process (MDP) and apply multi-agent reinforcement learning (MARL) algorithms to obtain dynamic TSC policies. We model each traffic signal junction as an independent agent. An agent decides the signal duration of its phases in a round-robin (RR) manner using multi-agent Q-learning with either is an element of-greedy or UCB 3] based exploration strategies. It updates its Q-factors based on the cost feedback signal received from its neighbouring agents. This feedback signal can be easily constructed and is shown to be effective in minimizing the average delay of the vehicles in the network. We show through simulations over VISSIM that our algorithms perform significantly better than both the standard fixed signal timing (FST) algorithm and the saturation balancing (SAT) algorithm 15] over two real road networks.

An ultrastable conjugate of silver nanoparticles and protein formed through weak interactions

In recent years, silver nanoparticles (AgNPs) have attracted significant attention owing to their unique physicochemical, optical, conductive and antimicrobial properties. One of the properties of AgNPs which is crucial for all applications is their stability. In the present study we unravel a mechanism through which silver nanoparticles are rendered ultrastable in an aqueous solution in complex with the protein ubiquitin (Ubq). This involves a dynamic and reversible association and dissociation of ubiquitin from the surface of AgNP. The exchange occurs at a rate much greater than 25 s(-1) implying a residence time of <40 ms for the protein. The AgNP-Ubq complex remains stable for months due to steric stabilization over a wide pH range compared to unconjugated AgNPs. NMR studies reveal that the protein molecules bind reversibly to AgNP with an approximate dissociation constant of 55 mu M and undergo fast exchange. At pH > 4 the positively charged surface of the protein comes in contact with the citrate capped AgNP surface. Further, NMR relaxation-based experiments suggest that in addition to the dynamic exchange, a conformational rearrangement of the protein takes place upon binding to AgNP. The ultrastability of the AgNP-Ubq complex was found to be useful for its anti-microbial activity, which allowed the recycling of this complex multiple times without the loss of stability. Altogether, the study provides new insights into the mechanism of protein-silver nanoparticle interactions and opens up new avenues for its application in a wide range of systems.

Origin of room temperature weak-ferromagnetism in antiferromagnetic Pb(Fe2/3W1/3)O-3 ceramic

We report the origin of room temperature weak ferromagnetic behavior of polycrystalline Pb(Fe2/3W1/3)O-3 (PFW) powder. The structure and magnetic properties of the ceramic powder prepared by a Columbite method were characterized by X-ray and neutron diffraction, Mossbauer spectroscopy and magnetization measurements. Rietveld analysis of diffraction data confirm the formation of single phase PFW, without traces of any parasitic pyrochlore phase. PFW was found to crystallize in the cubic structure at room temperature. The Rietveld refinement of neutron diffraction data measured at room temperature confirmed the G-type antiferromagnetic structure of PFW in our sample. However, along with the antiferromagnetic (AFM) ordering of the Fe spins, we have observed the existence of weak ferromagnetism at room temperature through: (i) a clear opening of hysteresis (M-H) loop, (ii) bifurcation of the field cooled and zero-field cooled susceptibility; supported by Mossbauer spectroscopy results. The P-E loop measurements showed a non-linear slim hysteresis loop at room temperature due to the electronic conduction through the local inhomogeneities in the PFW crystallites and the inter-particle regions. By corroborating all the magnetic measurements, especially the spin glass nature of the sample, with the conduction behavior of the sample, we report here that the observed ferromagnetism originates at these local inhomogeneous regions in the sample, where the Fe-spins are not perfectly aligned antiferromagnetically due to the compositional disordering. (C) 2015 Elsevier Ltd and Techna Group S.r.l. All rights reserved.