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.

Past Queue Length Based Low-Overhead Link Scheduling in Multi-beam Wireless Mesh Networks

Wireless mesh networks with multi-beam capability at each node through the use of multi-antenna beamforming are becoming practical and attracting increased research attention. Increased capacity due to spatial reuse and increased transmission range are potential benefits in using multiple directional beams in each node. In this paper, we are interested in low-complexity scheduling algorithms in such multi-beam wireless networks. In particular, we present a scheduling algorithm based on queue length information of the past slots in multi-beam networks, and prove its stability. We present a distributed implementation of this proposed algorithm. Numerical results show that significant improvement in delay performance is achieved using the proposed multi-beam scheduling compared to omni-beam scheduling. In addition, the proposed algorithm is shown to achieve a significant reduction in the signaling overhead compared to a current slot queue length approach.

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.

Proposed role of w chromosome inactivation and the absence of dosage compensation in avian sex determination

Three features of avian sex chromosomes - female heterogamety (ZZ male, ZW female), the apparently inactive state of the W chromosome, and dose-dependent expression of Z-linked genes - are examined in regard to their possible relation to sex determination. It is proposed that the W chromosome is facultatively heterochromatic and that the Z and W chromosomes carry one or more homologous sex-determination genes. The absence of dosage compensation in ZZ embryos, and W inactivation in ZW embryos, would then bring about a 2n(ZZ)-n(ZW) inequality in the effective copy number of such genes. The absence of dosage compensation of Z-linked genes in ZZ embryos is viewed as a means by which two copies of Z-W homologous sex determination genes are kept active to meet the requirements of testis determination. W inactivation may promote ovarian development by reducing the effective copy number of these genes from 2n to n. If there is a W-specific gene for femaleness, spread of heterochromatization to this gene in cells forming the right gonadal primordium may explain the latter's normally undifferentiated state; reversal of heterochromatization may similarly explain the development of the right gonad into a testis following left ovariectomy.

Synergistic interaction between particular X-chromosome deletions andSex-lethal causes female lethality inDrosophila melanogaster

We studied the effect on female viability of trans-heterozygous combinations of X-chromosome deficiencies and Sxt-(fl), a null allele of Sex-lethal. Twentyfive deficiencies, which together covered 80% of the X chromosome, were tested. Seven of these trans-heterozygous combinations caused significant levels of female lethality. Two of the seven interacting deficiencies include the previously known sex determination genes sans fille and sisterless-a. Four of the remaining uncover X-chromosomal regions that were not hitherto known to contain sex determination genes. These newly identified regions are defined by deficiencies Df(1)RA2 (7D10; 8A4-5), Df(1)KA14 (7F1-2; 8C6), Df(1)C52 (8E; 9C-D) and Df(1)N19 (17A1; 18A2). These four deficiencies were characterized further to determine whether it was the maternal or zygotic dosage that was primarily responsible for the observed lethality of female embryos, daughterless and extra macrochaetae, two known regulators of Sxl, influence the interaction of these deficiencies with Sxl.

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.

Levitation Effect: Role of Symmetry and Dependence of Diffusivity on the Bond Length of Homonuclear and Heteronuclear Diatomic Species

Molecular dynamics investigation of model diatomic species confined to the alpha-cages of zeolite NaY is reported. The dependence of self-diffusivity on the bond length of the diatomic species has been investigated. Three different sets of runs have been carried out. In the first set, the two atoms of the diatomic molecule interact with the zeolite atoms with equal strength (example, O-2, the symmetric case). In the second and third sets which correspond to asymmetric cases, the two atoms of the diatomic molecule interact with unequal strengths (example, CO). The result for the symmetric case exhibits a well-defined maximum in self-diffusivity for an intermediate bond length. In contrast to this, the intermediate asymmetry leads to a less pronounced maximum. For the large asymmetric case, the maximum is completely absent. These findings are analyzed by computing a number of related properties. These results provide a direct confirmation at the microscopic level of the suggestion by Derouane that the supermobility observed experimentally by Kemball has its origin in the mutual cancellation of forces. The maximum in diffusivity from molecular dynamics is seen at the value predicted by the levitation effect. Further, these findings suggest a role for symmetry in the existence of a diffusivity maximum as a function of diameter of the diffusant often referred to as the levitation effect. The nature of the required symmetry for the existence of anomalous diffusivity is interaction symmetry which is different from that normally encountered in crystallography.

Intermolecular complexes of singly linked bisporphyrins with trinitrobenzene

Several covalently linked bisporphyrin systems, free-base (H2P---H2P), hybrid bisporphyrins (Zn---H2P) and Zn(II) dimers (ZnP---ZnP) and their 1:1 molecular complexes with sym 1,3,5-trinitrobenzene have been investigated by optical absorption and emission, and magnetic resonance spectroscopic methods. In these systems, two porphyrin units are linked singly through one of the meso aryl groups via ether linkages of variable length. The bisporphyrins cooperatively bind a molecule of a ?-acceptor; 1,3,5-trinitrobenzene (TNB). The binding constant values vary with interchromophore separation. Maximum binding is observed in the bisporphyrin bearing a two-ether covalent linkage. It is found that TNB quenches the fluorescence of the two porphyrine units in a selective manner. It is suggested that a critical distance between the two porphyrin units is necessary for the observance of maximum cooperative intermolecular binding with an acceptor.

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.

Small Ubiquitin-related Modifier Ligase Activity of Mms21 Is Required for Maintenance of Chromosome Integrity during the Unperturbed Mitotic Cell Division Cycle in Saccharomyces cerevisiae

The SUMO ligase activity of Mms21/Nse2, a conserved member of the Smc5/6 complex, is required for resisting extrinsically induced genotoxic stress. We report that the Mms21 SUMO ligase activity is also required during the unchallenged mitotic cell cycle in Saccharomyces cerevisiae. SUMO ligase-defective cells were slow growing and spontaneously incurred DNA damage. These cells required caffeine-sensitive Mec1 kinase-dependent checkpoint signaling for survival even in the absence of extrinsically induced genotoxic stress. SUMO ligase-defective cells were sensitive to replication stress and displayed synthetic growth defects with DNA damage checkpoint-defective mutants such as mec1, rad9, and rad24. MMS21 SUMO ligase and mediator of replication checkpoint 1 gene (MRC1) were epistatic with respect to hydroxyurea-induced replication stress or methyl methanesulfonate-induced DNA damage sensitivity. Subjecting Mms21 SUMO ligase-deficient cells to transient replication stress resulted in enhancement of cell cycle progression defects such as mitotic delay and accumulation of hyperploid cells. Consistent with the spontaneous activation of the DNA damage checkpoint pathway observed in the Mms21-mediated sumoylation-deficient cells, enhanced frequency of chromosome breakage and loss was detected in these mutant cells. A mutation in the conserved cysteine 221 that is engaged in coordination of the zinc ion in Loop 2 of the Mms21 SPL-RING E3 ligase catalytic domain resulted in strong replication stress sensitivity and also conferred slow growth and Mec1 dependence to unchallenged mitotically dividing cells. Our findings establish Mms21-mediated sumoylation as a determinant of cell cycle progression and maintenance of chromosome integrity during the unperturbed mitotic cell division cycle in budding yeast.

Role of spacer chain length in dimeric micellar organization. Small angle neutron scattering and fluorescence studies

Micelles of different dimeric amphiphiles Br-, n-C(16)H(33)NMe(2)(+) -(CH)(m)-N(+)Me(2)-n-C16H33, Br- (where m = 3, 4, 5, 6, 8, 10, and 12) adapt different morphologies and internal packing arrangements in aqueous media depending on their spacer chain length (m). Detailed measurements of small angle neutron scattering (SANS) cross sections from different bis-cationic, dimeric surfactant micelles in aqueous media (D2O) are reported. The data have been analyzed using the Hayter and Penfold model for macro ion solution to compute the interparticle structure factor S(Q) taking into account the screened Coulomb interactions between the dimeric micelles. The SANS analysis clearly indicated that the extent of aggregate growth and the variations of shapes of the dimeric micelles depend primarily on the spacer chain length. With spacer chain length, m less than or equal to 4, the propensity of micellar growth was particularly pronounced. The effects of the variation of the concentration of dimeric surfactants with m = 5 and 10 on the SANS spectra and the effects of the temperature variation for the micellar system with m = 10 were also examined. The critical micelle concentrations (cmc) and their microenvironmental feature, namely, the microviscosities that the dimeric micellar aggregates offer to a solubilized, extrinsic fluorescence probe, 1,6-diphenyl-1,3,5-hexatriene, were also determined. The changes of cmcs and microviscosities as a function of spacer chain length have been explained in terms of conformational variations and progressive looping of the spacer in micellar core upon increasing m values.

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.