Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

Relative roles of instruction count and cycles per instruction in WCET estimation

Most of the existing WCET estimation methods directly estimate execution time, ET, in cycles. We propose to study ET as a product of two factors, ET = IC * CPI, where IC is instruction count and CPI is cycles per instruction. Considering directly the estimation of ET may lead to a highly pessimistic estimate since implicitly these methods may be using worst case IC and worst case CPI. We hypothesize that there exists a functional relationship between CPI and IC such that CPI=f(IC). This is ascertained by computing the covariance matrix and studying the scatter plots of CPI versus IC. IC and CPI values are obtained by running benchmarks with a large number of inputs using the cycle accurate architectural simulator, Simplescalar on two different architectures. It is shown that the benchmarks can be grouped into different classes based on the CPI versus IC relationship. For some benchmarks like FFT, FIR etc., both IC and CPI are almost a constant irrespective of the input. There are other benchmarks that exhibit a direct or an inverse relationship between CPI and IC. In such a case, one can predict CPI for a given IC as CPI=f(IC). We derive the theoretical worst case IC for a program, denoted as SWIC, using integer linear programming(ILP) and estimate WCET as SWIC*f(SWIC). However, if CPI decreases sharply with IC then measured maximum cycles is observed to be a better estimate. For certain other benchmarks, it is observed that the CPI versus IC relationship is either random or CPI remains constant with varying IC. In such cases, WCET is estimated as the product of SWIC and measured maximum CPI. It is observed that use of the proposed method results in tighter WCET estimates than Chronos, a static WCET analyzer, for most benchmarks for the two architectures considered in this paper.

Further results on geometric properties of a family of relative entropies

This paper extends some geometric properties of a one-parameter family of relative entropies. These arise as redundancies when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the Kullback-Leibler divergence. They satisfy the Pythagorean property and behave like squared distances. This property, which was known for finite alphabet spaces, is now extended for general measure spaces. Existence of projections onto convex and certain closed sets is also established. Our results may have applications in the Rényi entropy maximization rule of statistical physics.

A weight based context analysis system to provide a required UMM service

Ubiquitous Computing is an emerging paradigm which facilitates user to access preferred services, wherever they are, whenever they want, and the way they need, with zero administration. While moving from one place to another the user does not need to specify and configure their surrounding environment, the system initiates necessary adaptation by itself to cope up with the changing environment. In this paper we propose a system to provide context-aware ubiquitous multimedia services, without user’s intervention. We analyze the context of the user based on weights, identify the UMMS (Ubiquitous Multimedia Service) based on the collected context information and user profile, search for the optimal server to provide the required service, then adapts the service according to user’s local environment and preferences, etc. The experiment conducted several times with different context parameters, their weights and various preferences for a user. The results are quite encouraging.

A practical approach for cross-functional vehicle body weight optimization

The goal of optimization in vehicle design is often blurred by the myriads of requirements belonging to attributes that may not be quite related. If solutions are sought by optimizing attribute performance-related objectives separately starting with a common baseline design configuration as in a traditional design environment, it becomes an arduous task to integrate the potentially conflicting solutions into one satisfactory design. It may be thus more desirable to carry out a combined multi-disciplinary design optimization (MDO) with vehicle weight as an objective function and cross-functional attribute performance targets as constraints. For the particular case of vehicle body structure design, the initial design is likely to be arrived at taking into account styling, packaging and market-driven requirements. The problem with performing a combined cross-functional optimization is the time associated with running such CAE algorithms that can provide a single optimal solution for heterogeneous areas such as NVH and crash safety. In the present paper, a practical MDO methodology is suggested that can be applied to weight optimization of automotive body structures by specifying constraints on frequency and crash performance. Because of the reduced number of cases to be analyzed for crash safety in comparison with other MDO approaches, the present methodology can generate a single size-optimized solution without having to take recourse to empirical techniques such as response surface-based prediction of crash performance and associated successive response surface updating for convergence. An example of weight optimization of spaceframe-based BIW of an aluminum-intensive vehicle is given to illustrate the steps involved in the current optimization process.

Hybrid organogels and aerogels from co-assembly of structurally different low molecular weight gelators

The blending of perfluorinated bile ester derivatives with the gelator 2,3-didecyloxyanthracene (DDOA) yields a new class of hybrid organo- and aerogels displaying a combination of optical and mechanical properties that differ from those of pure gels. Indeed, the nanofibers constituting the hybrid organogels emit polarized blue light and display dichroic near-UV absorption via the achiral DDOA molecules, thanks to their association with a chiral bile ester. Moreover, the thermal stability and the mechanical yield stress of the mixed organogels in DMSO are enhanced for blends of DDOA with the deoxycholic gelator (DC11) having a C-11 chain, as compared to the pure components' gels. When the chain length of the ester is increased to C-13 (DC13) a novel compound for aerogel formation directly in scCO(2) is obtained under the studied conditions. A mixture of this compound with DDOA is also able to gelate scCO(2) leading to novel composite aerogel materials. As revealed by SAXS measurements, the hybrid and the pure DDOA and DC13 aerogels display cell parameters that are very similar. These SAXS experiments suggest that crystallographic conditions are very favorable for the growth of hybrid molecular arrangements in which DDOA and DC13 units could be interchanged. Specific molecular interactions between two components are not always a pre-requisite condition for the formation of a hybrid nanostructured material in which the components mutually induce properties.

Ages and relative sizes of pre-2004 tsunamis in the Bay of Bengal inferred from geologic evidence in the Andaman and Nicobar Islands

Geologic evidence along the northern part of the 2004 Aceh-Andaman rupture suggests that this region generated as many as five tsunamis in the prior 2000years. We identify this evidence by drawing analogy with geologic records of land-level change and the tsunami in 2004 from the Andaman and Nicobar Islands (A&N). These analogs include subsided mangrove swamps, uplifted coral terraces, liquefaction, and organic soils coated by sand and coral rubble. The pre-2004 evidence varies in potency, and materials dated provide limiting ages on inferred tsunamis. The earliest tsunamis occurred between the second and sixth centuries A.D., evidenced by coral debris of the southern Car Nicobar Island. A subsequent tsunami, probably in the range A.D. 770-1040, is inferred from deposits both in A&N and on the Indian subcontinent. It is the strongest candidate for a 2004-caliber earthquake in the past 2000years. A&N also contain tsunami deposits from A.D. 1250 to 1450 that probably match those previously reported from Sumatra and Thailand, and which likely date to the 1390s or 1450s if correlated with well-dated coral uplift offshore Sumatra. Thus, age data from A&N suggest that within the uncertainties in estimating relative sizes of paleo-earthquakes and tsunamis, the 1000year interval can be divided in half by the earthquake or earthquakes of A.D. 1250-1450 of magnitude >8.0 and consequent tsunamis. Unlike the transoceanic tsunamis generated by full or partial rupture of the subduction interface, the A&N geology further provides evidence for the smaller-sized historical tsunamis of 1762 and 1881, which may have been damaging locally.

Synthesis and application of weight function for edge cracked semicircular disk (ECSD)

We analyze the utility of edge cracked semicircular disk (ECSD) for rapid assessment of fracture toughness using compressive loading. Continuing our earlier work on ECSD, a theoretical examination here leads to a novel way for synthesizing weight functions using two distinct form factors. The efficacy of ECSD mode-I weight function synthesized using displacement and form factor methods is demonstrated by comparing with finite element results. Theory of elasticity in conjunction with finite element method is utilized to analyze crack opening potency of ECSD under eccentric compression to explore newer configurations of ECSD for fracture testing.

Integrated relative translation and rotation control of spacecraft formations

Formation flying of small spacecraft provides a way to improve the resolution by aperture distribution. This requires autonomous control of relative position and relative attitude. The present work addresses the formation control using a PID controller to maintain both relative position and relative attitude. To avoid continuous pulsing due to noise, a dead-band has been provided in the position loop. PID control has been selected to maintain the formation in the presence of unmodeled disturbances. Simulations show that the proposed controller meets the required translational and rotational relative motions even in the presence of disturbances.

RES-TOCSY: A facile approach for accurate determination of magnitudes, and relative signs of (n)J(HF)

The RES-TOCSY experiment for accurate determination of heteronuclear (n)J(HF) is reported. The main feature of the proposed technique is the accurate measurement of magnitudes of heteronuclear couplings from the displacement of cross sections of the 2D spectrum and their relative signs from the slopes of their displacement vectors. The experiment is highly advantageous as the couplings of smaller magnitudes hidden within line widths could also be accurately determined, and also in situations when the spectrum does not display any coupling fine structures. The efficient utility of the developed pulse sequence is unambiguously established on fluorine containing aromatic and aliphatic molecules. (C) 2014 Elsevier B.V. All rights reserved.

Ranking of global climate models for India using multicriterion analysis

Eleven GCMs (BCCR-BCCM2.0, INGV-ECHAM4, GFDL2.0, GFDL2.1, GISS, IPSL-CM4, MIROC3, MRI-CGCM2, NCAR-PCMI, UKMO-HADCM3 and UKMO-HADGEM1) were evaluated for India (covering 73 grid points of 2.5 degrees x 2.5 degrees) for the climate variable `precipitation rate' using 5 performance indicators. Performance indicators used were the correlation coefficient, normalised root mean square error, absolute normalised mean bias error, average absolute relative error and skill score. We used a nested bias correction methodology to remove the systematic biases in GCM simulations. The Entropy method was employed to obtain weights of these 5 indicators. Ranks of the 11 GCMs were obtained through a multicriterion decision-making outranking method, PROMETHEE-2 (Preference Ranking Organisation Method of Enrichment Evaluation). An equal weight scenario (assigning 0.2 weight for each indicator) was also used to rank the GCMs. An effort was also made to rank GCMs for 4 river basins (Godavari, Krishna, Mahanadi and Cauvery) in peninsular India. The upper Malaprabha catchment in Karnataka, India, was chosen to demonstrate the Entropy and PROMETHEE-2 methods. The Spearman rank correlation coefficient was employed to assess the association between the ranking patterns. Our results suggest that the ensemble of GFDL2.0, MIROC3, BCCR-BCCM2.0, UKMO-HADCM3, MPIECHAM4 and UKMO-HADGEM1 is suitable for India. The methodology proposed can be extended to rank GCMs for any selected region.

Ovarian development in a primitively eusocial wasp: Social interactions affect behaviorally dominant and subordinate wasps in opposite directions relative to solitary females

In many primitively eusocial wasp species new nests are founded either by a single female or by a small group of females. In the single foundress nests, the lone female develops her ovaries, lays eggs as well as tends her brood. In multiple foundress nests social interactions, especially dominance-subordinate interactions, result in only one `dominant' female developing her ovaries and laying eggs. Ovaries of the remaining `subordinate' cofoundresses remain suppressed and these individuals function as workers and tend the dominant's brood. Using the tropical, primitively eusocial polistine wasp Ropalidia marginata and by comparing wasps held in isolation and those kept as pairs in the laboratory, we demonstrate that social interactions affect ovarian development of dominant and subordinate wasps among the pairs in opposite directions, suppressing the ovaries of the subordinate member of the pair below that of solitary wasps and boosting the ovaries of dominant member of the pair above that of solitary females. In addition to being of physiological interest, such mirror image effects of aggression on the ovaries of the aggressors and their victims, suggest yet another mechanism by which subordinates can enhance their indirect fitness and facilitate the evolution of worker behavior by kin selection. (C) 2014 Elsevier B.V. All rights reserved.

Combinatorial effect of rolling and carbonaceous nanoparticles on the evolution of crystallographic texture and structural properties of ultra high molecular weight polyethylene

Ultra high molecular weight polyethylene (PE) is a structural polymer widely used in biomedical implants. The mechanical properties of PE can be improved either by controlled crystalline orientation (texture) or by the addition of reinforcing agents. However, the combinatorial effect has not received much attention. The objective of this study was to characterize the structure and mechanical properties of PE composites incorporating multiwall carbon nanotubes (MWCNT) and reduced graphene oxide (RGO) subjected to hot rolling. The wide angle X-ray diffraction studies revealed that mechanical deformation resulted in a mixture of orthorhombic and monoclinic crystals. Furthermore, the presence of nanoparticles resulted in lower crystallinity in PE with smaller crystallite size, more so in RGO than in MWCNT composites. Rolling strengthened the texture of both orthorhombic and the monoclinic phases in PE. Presence of RGO weakened the texture of both phases of PE after rolling whereas MWCNT only mildly weakened the texture. This resulted in a reduction in the elastic modulus of RGO composites whereas moduli of neat polymer and the MWCNT composite increased after rolling. This study provides new insight into the role of nanoparticles in texture evolution during polymer processing with implications for processing of structural polymer composites.

Relative entropy in higher spin holography

We examine relative entropy in the context of the higher spin/CFT duality. We consider 3D bulk configurations in higher spin gravity which are dual to the vacuum and a high temperature state of a CFT with W-algebra symmetries in the presence of a chemical potential for a higher spin current. The relative entropy between these states is then evaluated using the Wilson line functional for holographic entanglement entropy. In the limit of small entangling intervals, the relative entropy should vanish for a generic quantum system. We confirm this behavior by showing that the difference in the expectation values of the modular Hamiltonian between the states matches with the difference in the entanglement entropy in the short-distance regime. Additionally, we compute the relative entropy of states corresponding to smooth solutions in the SL(2, Z) family with respect to the vacuum.

Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.