A Convex Optimization Framework for Almost Budget Balanced Allocation of a Divisible Good

We address the problem of allocating a single divisible good to a number of agents. The agents have concave valuation functions parameterized by a scalar type. The agents report only the type. The goal is to find allocatively efficient, strategy proof, nearly budget balanced mechanisms within the Groves class. Near budget balance is attained by returning as much of the received payments as rebates to agents. Two performance criteria are of interest: the maximum ratio of budget surplus to efficient surplus, and the expected budget surplus, within the class of linear rebate functions. The goal is to minimize them. Assuming that the valuation functions are known, we show that both problems reduce to convex optimization problems, where the convex constraint sets are characterized by a continuum of half-plane constraints parameterized by the vector of reported types. We then propose a randomized relaxation of these problems by sampling constraints. The relaxed problem is a linear programming problem (LP). We then identify the number of samples needed for ``near-feasibility'' of the relaxed constraint set. Under some conditions on the valuation function, we show that value of the approximate LP is close to the optimal value. Simulation results show significant improvements of our proposed method over the Vickrey-Clarke-Groves (VCG) mechanism without rebates. In the special case of indivisible goods, the mechanisms in this paper fall back to those proposed by Moulin, by Guo and Conitzer, and by Gujar and Narahari, without any need for randomization. Extension of the proposed mechanisms to situations when the valuation functions are not known to the central planner are also discussed. Note to Practitioners-Our results will be useful in all resource allocation problems that involve gathering of information privately held by strategic users, where the utilities are any concave function of the allocations, and where the resource planner is not interested in maximizing revenue, but in efficient sharing of the resource. Such situations arise quite often in fair sharing of internet resources, fair sharing of funds across departments within the same parent organization, auctioning of public goods, etc. We study methods to achieve near budget balance by first collecting payments according to the celebrated VCG mechanism, and then returning as much of the collected money as rebates. Our focus on linear rebate functions allows for easy implementation. The resulting convex optimization problem is solved via relaxation to a randomized linear programming problem, for which several efficient solvers exist. This relaxation is enabled by constraint sampling. Keeping practitioners in mind, we identify the number of samples that assures a desired level of ``near-feasibility'' with the desired confidence level. Our methodology will occasionally require subsidy from outside the system. We however demonstrate via simulation that, if the mechanism is repeated several times over independent instances, then past surplus can support the subsidy requirements. We also extend our results to situations where the strategic users' utility functions are not known to the allocating entity, a common situation in the context of internet users and other problems.

Identification of a core promoter and a novel isoform of the human TSCI gene transcript and structural comparison with mouse homolog

Tuberous sclerosis complex (TSC) is an autosomal dominant disorder with loci on chromosome 9q34.12 (TSC1) and chromosome 16p13.3 (TSC2). Genes for both loci have been isolated and characterized. The promoters of both genes have not been characterized so far and little is known about the regulation of these genes. This study reports the characterization of the human TSC1 promoter region for the first time. We have identified a novel alternative isoform in the 5' untranslated region (UTR) of the TSC1 gene transcript involving exon 1. Alternative isoforms in the 5' UTR of the mouse Tsc1 gene transcript involving exon I and exon 2 have also been identified. We have identified three upstream open reading frames (uORFs) in the 5' UTR of the TSC1/Tsc1 gene. A comparative study of the 5' UTR of TSC1/Tsc1 gene has revealed that there is a high degree of similarity not only in the sequence but also in the splicing pattern of both human and mouse TSC1 genes. We have used PCR methodology to isolate approximately 1.6 kb genomic DNA 5' to the TSC1 cDNA. This sequence has directed a high level of expression of luciferase activity in both HeLa and HepG2 cells. Successive 5' and 3' deletion analysis has suggested that a -587 bp region, from position +77 to -510 from the transcription start site (TSS), contains the promoter activity. Interestingly, this region contains no consensus TATA box or CAAT box. However, a 521-bp fragment surrounding the TSS exhibits the characteristics of a CpG island which overlaps with the promoter region. The identification of the TSC1 promoter region will help in designing a suitable strategy to identify mutations in this region in patients who do not show any mutations in the coding regions. It will also help to study the regulation of the TSC1 gene and its role in tumorigenesis. (C) 2003 Elsevier B.V. All rights reserved.

Structural changes in single-walled carbon nanotubes under non-hydrostatic pressures: x-ray and Raman studies

Using in situ x-ray diffraction and Raman scattering techniques, we have investigated the behaviour of single-walled carbon nanotubes bundles under non-hydrostatic pressures. It is seen that the diffraction line corresponding to the two-dimensional triangular lattice in the bundles is not reversible for pressures beyond 5 GPa, in sharp contrast to earlier results under hydrostatic pressure conditions. Most interestingly, radial breathing and tangential Raman modes of the pressure-cycled samples from 21 and 30 GPa match very well with those of the starting sample. Raman and x-ray results put together clearly suggest that the ordering of tubes in the bundles is only marginally regained with a very short coherence length on decompression.

Structural characterization of DC magnetron-sputtered TiO2 thin films using XRD and Raman scattering studies

Titanium dioxide films have been deposited using DC magnetron sputtering technique onto well-cleaned p-silicon substrates at an oxygen partial pressure of 7 x 10(-5) mbar and at a sputtering pressure (Ar + O-2) Of I X 10(-3) mbar. The deposited films were calcinated at 673 and 773 K. The composition of the films as analyzed using Auger electron spectroscopy reveals the stoichiometry with an 0 and Ti ratio 2.08. The influence of post-deposition annealing at 673 and 773 K on the structural properties of the titanium dioxide thin films have been studied using XRD and Raman scattering. The structure of the films deposited at the ambient was found to be amorphous and the films annealed at temperature 673 K and above were crystalline with anatase structure. The lattice constants, grain size, microstrain and the dislocation density of the film are calculated and correlated with annealing temperature. The Raman scattering study was performed on the as-deposited and annealed samples and the existence of Raman active modes A(1g), B-1g and E-g corresponding to the Raman shifts are studied and reported. The improvement of crystallinity of the TiO2 films was also studied using Raman scattering studies. (C) 2003 Elsevier Ltd. All rights reserved.

Studies on the structural and ionic transport properties at elevated temperatures of La1-xMnO3 +/-delta synthesized by a wet chemical method

Structural transformation and ionic transport properties are investigated on wet-chemically synthesized La1-xMnO3 (X=0.0-0.18) compositions. Powders annealed in oxygen/air at 1000-1080 K exhibit cubic symmetry and transform to rhombohedral on annealing at 1173-1573 K in air/oxygen. Annealing above 1773 K in air or in argon/helium at 1473 K stabilized distorted rhombohedral or orthorhombic symmetry. Structural transformations are confirmed from XRD and TEM studies. The total conductivity of sintered disks, measured by four-probe technique, ranges from 5 S cm(-1) at 298 K to 105 S cm(-1) at 1273 K. The ionic conductivity measured by blocking electrode technique ranges from 1.0X10(-6) S cm(-1) at 700 K to 2.0X10(-3) S cm(-1) at 1273 K. The ionic transference number of these compositions ranges from 3.0X10(-5) to 5.0X10(-5) at 1273 K. The activation energy deduced from experimental data for ionic conduction and ionic migration is 1.03-1.10 and 0.80-1.00 eV, respectively. The activation energy of formation, association and migration of vacancies ranges from 1.07 to 1.44 eV. (C) 2002 Elsevier Science B.V. All rights reserved.

Weak interactions involving organic fluorine: analysis of structural motifs in Flunazirine and Haloperidol

The crystal structure of Flunazirine, an anticonvulsant drug, is analyzed in terms of intermolecular interactions involving fluorine. The structure displays motifs formed by only weak interactions C–H⋯F and C–H⋯π. The motifs thus generated show cavities, which could serve as hosts for complexation. The structure of Flunazirine displays cavities formed by C–H⋯F and C–H⋯π interactions. Haloperidol, an antipsychotic drug, shows F⋯F interactions in the crystalline lattice in lieu of Cl⋯Cl interactions. However, strong O–H⋯N interactions dominate packing. The salient features of the two structures in terms of intermolecular interactions reveal, even though organic fluorine has lower tendency to engage in hydrogen bonding and F⋯F interactions, these interactions could play a significant role in the design of molecular assemblies via crystal engineering.

Effect of annealing temperature on electrical and nano-structural properties of sol-gel derived ZnO thin films

Zinc oxide (ZnO) thin films have been prepared on silicon substrates by sol-gel spin coating technique with spinning speed of 3,000 rpm. The films were annealed at different temperatures from 200 to 500 A degrees C and found that ZnO films exhibit different nanostructures at different annealing temperatures. The X-ray diffraction (XRD) results showed that the ZnO films convert from amorphous to polycrystalline phase after annealing at 400 A degrees C. The metal oxide semiconductor (MOS) capacitors were fabricated using ZnO films deposited on pre-cleaned silicon (100) substrates and electrical properties such as current versus voltage (I-V) and capacitance versus voltage (C-V) characteristics were studied. The electrical resistivity decreased with increasing annealing temperature. The oxide capacitance was measured at different annealing temperatures and different signal frequencies. The dielectric constant and the loss factor (tan delta) were increased with increase of annealing temperature.

Improvement of protein structure comparison using a structural alphabet

The three dimensional structure of a protein provides major insights into its function. Protein structure comparison has implications in functional and evolutionary studies. A structural alphabet (SA) is a library of local protein structure prototypes that can abstract every part of protein main chain conformation. Protein Blocks (PBS) is a widely used SA, composed of 16 prototypes, each representing a pentapeptide backbone conformation defined in terms of dihedral angles. Through this description, the 3D structural information can be translated into a 1D sequence of PBs. In a previous study, we have used this approach to compare protein structures encoded in terms of PBs. A classical sequence alignment procedure based on dynamic programming was used, with a dedicated PB Substitution Matrix (SM). PB-based pairwise structural alignment method gave an excellent performance, when compared to other established methods for mining. In this study, we have (i) refined the SMs and (ii) improved the Protein Block Alignment methodology (named as iPBA). The SM was normalized in regards to sequence and structural similarity. Alignment of protein structures often involves similar structural regions separated by dissimilar stretches. A dynamic programming algorithm that weighs these local similar stretches has been designed. Amino acid substitutions scores were also coupled linearly with the PB substitutions. iPBA improves (i) the mining efficiency rate by 6.8% and (ii) more than 82% of the alignments have a better quality. A higher efficiency in aligning multi-domain proteins could be also demonstrated. The quality of alignment is better than DALI and MUSTANG in 81.3% of the cases. Thus our study has resulted in an impressive improvement in the quality of protein structural alignment. (C) 2011 Elsevier Masson SAS. All rights reserved.

The biological and structural characterization of Mycobacterium tuberculosis UvrA provides novel insights into its mechanism of action

Mycobacterium tuberculosis is an extremely well adapted intracellular human pathogen that is exposed to multiple DNA damaging chemical assaults originating from the host defence mechanisms. As a consequence, this bacterium is thought to possess highly efficient DNA repair machineries, the nucleotide excision repair (NER) system amongst these. Although NER is of central importance to DNA repair in M. tuberculosis, our understanding of the processes in this species is limited. The conserved UvrABC endonuclease represents the multi-enzymatic core in bacterial NER, where the UvrA ATPase provides the DNA lesion-sensing function. The herein reported genetic analysis demonstrates that M. tuberculosis UvrA is important for the repair of nitrosative and oxidative DNA damage. Moreover, our biochemical and structural characterization of recombinant M. tuberculosis UvrA contributes new insights into its mechanism of action. In particular, the structural investigation reveals an unprecedented conformation of the UvrB-binding domain that we propose to be of functional relevance. Taken together, our data suggest UvrA as a potential target for the development of novel anti-tubercular agents and provide a biochemical framework for the identification of small-molecule inhibitors interfering with the NER activity in M. tuberculosis.

Unified Vdd Vth Optimization Based DVFM Controller for a Logic Block

In this paper analytical expressions for optimal Vdd and Vth to minimize energy for a given speed constraint are derived. These expressions are based on the EKV model for transistors and are valid in both strong inversion and sub threshold regions. The effect of gate leakage on the optimal Vdd and Vth is analyzed. A new gradient based algorithm for controlling Vdd and Vth based on delay and power monitoring results is proposed. A Vdd-Vth controller which uses the algorithm to dynamically control the supply and threshold voltage of a representative logic block (sum of absolute difference computation of an MPEG decoder) is designed. Simulation results using 65 nm predictive technology models are given.