Popular matchings with variable item copies

We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching M* is popular if there is no matching M such that the number of people who prefer M to M* exceeds the number who prefer M* to M. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: Given a graph G = (A U 3, E) where A is the set of people and 2 is the set of items, and a list < c(1),...., c(vertical bar B vertical bar)> denoting upper bounds on the number of copies of each item, does there exist < x(1),...., x(vertical bar B vertical bar)> such that for each i, having x(i) copies of the i-th item, where 1 <= xi <= c(i), enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c(i) is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer k. (C) 2011 Elsevier B.V. All rights reserved.

Variable Elimination in Linear Constraints

Gauss and Fourier have together provided us with the essential techniques for symbolic computation with linear arithmetic constraints over the reals and the rationals. These variable elimination techniques for linear constraints have particular significance in the context of constraint logic programming languages that have been developed in recent years. Variable elimination in linear equations (Guassian Elimination) is a fundamental technique in computational linear algebra and is therefore quite familiar to most of us. Elimination in linear inequalities (Fourier Elimination), on the other hand, is intimately related to polyhedral theory and aspects of linear programming that are not quite as familiar. In addition, the high complexity of elimination in inequalities has forces the consideration of intricate specializations of Fourier's original method. The intent of this survey article is to acquaint the reader with these connections and developments. The latter part of the article dwells on the thesis that variable elimination in linear constraints over the reals extends quite naturally to constraints in certain discrete domains.

Identification of Local Conformational Similarity in Structurally Variable Regions of Homologous Proteins Using Protein Blocks

Structure comparison tools can be used to align related protein structures to identify structurally conserved and variable regions and to infer functional and evolutionary relationships. While the conserved regions often superimpose well, the variable regions appear non superimposable. Differences in homologous protein structures are thought to be due to evolutionary plasticity to accommodate diverged sequences during evolution. One of the kinds of differences between 3-D structures of homologous proteins is rigid body displacement. A glaring example is not well superimposed equivalent regions of homologous proteins corresponding to a-helical conformation with different spatial orientations. In a rigid body superimposition, these regions would appear variable although they may contain local similarity. Also, due to high spatial deviation in the variable region, one-to-one correspondence at the residue level cannot be determined accurately. Another kind of difference is conformational variability and the most common example is topologically equivalent loops of two homologues but with different conformations. In the current study, we present a refined view of the ``structurally variable'' regions which may contain local similarity obscured in global alignment of homologous protein structures. As structural alphabet is able to describe local structures of proteins precisely through Protein Blocks approach, conformational similarity has been identified in a substantial number of `variable' regions in a large data set of protein structural alignments; optimal residue-residue equivalences could be achieved on the basis of Protein Blocks which led to improved local alignments. Also, through an example, we have demonstrated how the additional information on local backbone structures through protein blocks can aid in comparative modeling of a loop region. In addition, understanding on sequence-structure relationships can be enhanced through our approach. This has been illustrated through examples where the equivalent regions in homologous protein structures share sequence similarity to varied extent but do not preserve local structure.

Propagating intensity disturbances in polar corona as seen from AIA/SDO

Context. Polar corona is often explored to find the energy source for the acceleration of the fast solar wind. Earlier observations show omni-presence of quasi-periodic disturbances, traveling outward, which is believed to be caused by the ubiquitous presence of outward propagating waves. These waves, mostly of compressional type, might provide the additional momentum and heat required for the fast solar wind acceleration. It has been conjectured that these disturbances are not due to waves but high speed plasma outflows, which are difficult to distinguish using the current available techniques. Aims. With the unprecedented high spatial and temporal resolution of AIA/SDO, we search for these quasi-periodic disturbances in both plume and interplume regions of the polar corona. We investigate their nature of propagation and search for a plausible interpretation. We also aim to study their multi-thermal nature by using three different coronal passbands of AIA. Methods. We chose several clean plume and interplume structures and studied the time evolution of specific channels by making artificial slits along them. Taking the average across the slits, space-time maps are constructed and then filtration techniques are applied to amplify the low-amplitude oscillations. To suppress the effect of fainter jets, we chose wider slits than usual. Results. In almost all the locations chosen, in both plume and interplume regions we find the presence of propagating quasi-periodic disturbances, of periodicities ranging from 10-30 min. These are clearly seen in two channels and in a few cases out to very large distances (approximate to 250 `') off-limb, almost to the edge of the AIA field of view. The propagation speeds are in the range of 100-170 km s(-1). The average speeds are different for different passbands and higher in interplume regions. Conclusions. Propagating disturbances are observed, even after removing the effects of jets and are insensitive to changes in slit width. This indicates that a coherent mechanism is involved. In addition, the observed propagation speed varies between the different passpands, implying that these quasi-periodic intensity disturbances are possibly due to magneto-acoustic waves. The propagation speeds in interplume region are higher than in the plume region.

Unsteady nonsimilar two-dimensional and axisymmetric water boundary layers with variable viscosity and prandtl number

The influence of temperature-dependent viscosity and Prandtl number on the unsteady laminar nonsimilar forced convection flow over two-dimensional and axisymmetric bodies has been examined where the unsteadiness and (or) nonsimilarity are (is) due to the free stream velocity, mass transfer, and transverse curvature. The partial differential equations governing the flow which involve three independent variables have been solved numerically using an implicit finite-difference scheme along with a quasilinearization technique. It is found that both the skin friction and heat transfer strongly respond to the unsteady free stream velocity distributions. The unsteadiness and injection cause the location of zero skin friction to move upstream. However, the effect of variable viscosity and Prandtl number is to move it downstream. The heat transfer is found to depend strongly on viscous dissipation, but the skin friction is little affected by it. In general, the results pertaining to variable fluid properties differ significantly, from those of constant fluid properties.

Variable density approach for rotating shallow shell of variable thickness

A new approach based on variable density in conjunction with shallow shell theory is proposed to analyse rotating shallow shell of variable thickness. Coupled non-linear ordinary differential equations governing shallows shells of variable thickness are first derived before applying the variable density approach. Results obtained from the new approach compare well with FEM calculation for a wide range of profiles considered in this paper.

Variable Sparsity Kernel Learning

This paper(1) presents novel algorithms and applications for a particular class of mixed-norm regularization based Multiple Kernel Learning (MKL) formulations. The formulations assume that the given kernels are grouped and employ l(1) norm regularization for promoting sparsity within RKHS norms of each group and l(s), s >= 2 norm regularization for promoting non-sparse combinations across groups. Various sparsity levels in combining the kernels can be achieved by varying the grouping of kernels-hence we name the formulations as Variable Sparsity Kernel Learning (VSKL) formulations. While previous attempts have a non-convex formulation, here we present a convex formulation which admits efficient Mirror-Descent (MD) based solving techniques. The proposed MD based algorithm optimizes over product of simplices and has a computational complexity of O (m(2)n(tot) log n(max)/epsilon(2)) where m is no. training data points, n(max), n(tot) are the maximum no. kernels in any group, total no. kernels respectively and epsilon is the error in approximating the objective. A detailed proof of convergence of the algorithm is also presented. Experimental results show that the VSKL formulations are well-suited for multi-modal learning tasks like object categorization. Results also show that the MD based algorithm outperforms state-of-the-art MKL solvers in terms of computational efficiency.

The effect of surface mass transfer on buoyancy induced flow in a variable porosity medium adjacent to a vertical heated plate

The effect of surface mass transfer on buoyancy induced flow in a variable porosity medium adjacent to a heated vertical plate is studied for high Rayleigh numbers. Similarity solutions are obtained within the frame work of boundary layer theory for a power law variation in surface temperature,T Wpropx lambda and surface injectionv Wpropx(lambda–1/2). The analysis incorporates the expression connecting porosity and permeability and also the expression connecting porosity and effective thermal diffusivity. The influence of thermal dispersion on the flow and heat transfer characteristics are also analysed in detail. The results of the present analysis document the fact that variable porosity enhances heat transfer rate and the magnitude of velocity near the wall. The governing equations are solved using an implicit finite difference scheme for both the Darcy flow model and Forchheimer flow model, the latter analysis being confined to an isothermal surface and an impermeable vertical plate. The influence of the intertial terms in the Forchheimer model is to decrease the heat transfer and flow rates and the influence of thermal dispersion is to increase the heat transfer rate.

Syntheses, Transfection Efficacy and Cell Toxicity Properties of Novel Cholesterol-based Gemini Lipids having Hydroxyethyl Head group

We have synthesized five new cholesterol based gemini cationic lipids possessing hydroxyethyl (-CH2CH2OH) function on each head group, which differ in the length of the polymethylene spacer chain. These gemini lipids are important for gene delivery processes as they possess pre-optimized molecular features, e. g., cholesterol backbone, ether linkage and a variable spacer chain between both the headgroups of the gemini lipids. Cationic liposomes were prepared from each of these lipids individually and as a mixture of individual cationic gemini lipid and 1,2-dioleoyl phosphatidylethanolamine (DOPE). Each gemini lipid based formulation induced better transfection activity than that of their monomeric counterpart. One such gemini lipid with a -(CH2)(12)-spacer, HG-12, showed dramatic increase in the mean fluorescence intensity due to the expression of green-fluorescence protein (GFP) in the presence of 10% FBS compared to the conditions where there was no serum. Other gemini lipids retained their gene transfection efficiency without any marked decrease in the presence of serum. The only exception was seen with the gemini with a -(CH2)(3)-spacer, HG-3, which on gene transfection in the presence of 10% FBS lost similar to 70% of its transfection efficiency. Overall the gemini lipid with a -(CH2)(5)-spacer, HG-5, showed the highest transfection activity at N/P (lipid/DNA) ratio of 0.5 and lipid : DOPE molar ratio of 2. Upon comparison of the relevant parameters, e. g., %-transfected cells, the amount of DNA transfected to each cell and %-cell viability all together against Lipofectamine 2000, one of the best commercial transfecting agents, the optimized lipid formulation based on DOPE/HG-5 was found to be comparable. In terms of its ability to induce gene-transfer in the presence of serum and shelf-life DOPE/HG-5 liposome was found to be superior to its commercial counterpart. Confocal imaging analysis confirmed that in the presence of 10% serum using a Lipid : DOPE of 1 : 4 and N/P charge ratio of 0.75 with 1.2 mu g DNA per well, HG-5 is better than Lipofectamine 2000.

Autoignition in a non-premixed medium: DNS studies on the effects of three-dimensional turbulence

Direct numerical simulation (DNS) results of autoignition in anon-premixed medium under an isotropic, homogeneous, and decaying turbulence are presented. The initial mixture consists of segregated fuel parcels randomly distributed within warm air, and the entire medium is subjected to a three-dimensional turbulence. Chemical kinetics is modeled by a four-step reduced reaction mechanism for autoignition of n-heptane/air mixture. Thus, this work overcomes the principal limitations of a previous contribution of the authors on two-dimensional DNS of autoignition with a one-step reaction model. Specific attention is focused on the differences in the effects of two- and three-dimensional turbulence on autoignition characteristics. The three-dimensional results show that ignition spots are most likely to originate at locations jointly corresponding to the most reactive mixture fraction and low scalar dissipation rate. Further, these ignition spots are found to originate at locations corresponding to the core of local vortical structures, and after ignition, the burning gases move toward the vortex periphery Such a movement is explained as caused by the cyclostrophic imbalance developed when the local gas density is variable. These results lead to the conclusion that the local ignition-zone structure does not conform to the classical stretched flamelet description. Parametric studies show that the ignition delay time decreases with an increase in turbulence intensity. Hence, these three-dimensional simulation results resolve the discrepancy between trends in experimental data and predictions from DNSs of two-dimensional turbulence. This qualitative difference between DNS results from three- and two-dimensional simulations is discussed and attributed to the effect of vortex stretching that is present in the former, but not in the latter.

Critical stress intensity factors for cracked hollow pipes under transient thermal loads

Finite element analyses of a long hollow cylinder having an axisymmetric circumferential internal edge crack, subjected to convective cooling on the inner surface are performed. The transient thermal stress intensity factor is estimated using a domain version of the J-integral method. The effect of the thickness of the cylinder, crack length, and heat transfer coefficient on the stress intensity factor history are studied. The variations of critical normalized stress intensity factor with crack length-to-thickness ratio for different parameters are presented. The results show that if a small inner surface crack begins to grow, its stress intensity factor will increase with increase in crack length, reach a maximum, and then begin to drop. Based on the results, a fracture-based design methodology for cracked hollow pipes under transient thermal loads is discussed.

Investigation of short-time isomerization dynamics in p-nitroazobenzene from resonance Raman intensity analysis

Resonance Raman (RR) spectra are presented for p-nitroazobenzene dissolved in chloroform using 18 excitation Wavelengths, covering the region of (1)(n --> pi*) electronic transition. Raman intensities are observed for various totally symmetric fundamentals, namely, C-C, C-N, N=N, and N-O stretching vibrations, indicating that upon photoexcitation the excited-state evolution occurs along all of these vibrational coordinates. For a few fundamentals, interestingly, in p-nitroazobenzene, it is observed that the RR intensities decrease near the maxima of the resonant electronic (1)(n --> pi*) transition. This is attributed to the interference from preresonant scattering due to the strongly allowed (1)(pi --> pi*) electronic transition. The electronic absorption spectrum and the absolute Raman cross section for the nine Franck-Condon active fundamentals of p-nitroazobenzene have been successfully modeled using Heller's time-dependent formalism for Raman scattering. This employs harmonic description of the lowest energy (1)(n --> pi*) potential energy surface. The short-time isomerization dynamics is then examined from a priori knowledge of the ground-state normal mode descriptions of p-nitroazobenzene to convert the wave packet motion in dimensionless normal coordinates to internal coordinates. It is observed that within 20 fs after photoexcitation in p-nitroazobenzene, the N=N and C-N stretching vibrations undergo significant changes and the unsubstituted phenyl ring and the nitro stretching vibrations are also distorted considerably.

Studies on a new high-intensity low-emission burner

This paper presents computational and experimental results on a new burner configuration with a mild combustion concept with heat release rates up to 10 MW/m(3). The burner configuration is shown to achieve mild combustion by using air at ambient temperature at high recirculation rates (similar to250%-290%) both experimentally and computationally. The principal features of the configuration are: (1) a burner with forward exit for exhaust gases; (2) injection of gaseous fuel and air as multiple, alternate, peripheral highspeed jets at the bottom at ambient temperature, thus creating high enough recirculation rates of the hot combustion products into fresh incoming reactants; and (3) use of a suitable geometric artifice-a frustum of a cone to help recirculation. The computational studies have been used to reveal the details of the flow and to optimize the combustor geometry based on recirculation rates. Measures, involving root mean square temperature fluctuations, distribution of temperature and oxidizer concentration inside the proposed burner, and a classical turbulent diffusion jet flame, are used to distinguish between them quantitatively. The system, operated at heat release rates of 2 to 10 MW/m(3) (compared to 0.02 to 0.32 MW/m(3) in the earlier studies), shows a 10-15 dB reduction in noise in the mild combustion mode compared to a simple open-top burner and exhaust NOx emission below 10 ppm for a 3 kW burner with 10% excess air. The peak temperature is measured around 1750 K, approximately 300 K lower than the peak temperature in a conventional burner.

Variable-speed wind power generation using doubly fed wound rotor induction machine - A comparison with alternative schemes

In this paper, a wind energy conversion system (WECS) using grid-connected wound rotor induction machine controlled from the rotor side is compared with both fixed speed and variable speed systems using cage rotor induction machine. The comparison is done on the basis of (I) major hardware components required, (II) operating region, and (III) energy output due to a defined wind function using the characteristics of a practical wind turbine. Although a fixed speed system is more simple and reliable, it severely limits the energy output of a wind turbine. In case of variable speed systems, comparison shows that using a wound rotor induction machine of similar rating can significantly enhance energy capture. This comes about due to the ability to operate with rated torque even at supersynchronous speeds; power is then generated out of the rotor as well as the stator. Moreover, with rotor side control, the voltage rating of the power devices and dc bus capacitor bank is reduced. The size of the line side inductor also decreasesd. Results are presented to show the substantial advantages of the doubly fed system.