An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

Local search multiuser detection

In this work, a wide analysis of local search multiuser detection (LS-MUD) for direct sequence/code division multiple access (DS/CDMA) systems under multipath channels is carried out considering the performance-complexity trade-off. It is verified the robustness of the LS-MUD to variations in loading, E(b)/N(0), near-far effect, number of fingers of the Rake receiver and errors in the channel coefficients estimates. A compared analysis of the bit error rate (BER) and complexity trade-off is accomplished among LS, genetic algorithm (GA) and particle swarm optimization (PSO). Based on the deterministic behavior of the LS algorithm, it is also proposed simplifications over the cost function calculation, obtaining more efficient algorithms (simplified and combined LS-MUD versions) and creating new perspectives for the MUD implementation. The computational complexity is expressed in terms of the number of operations in order to converge. Our conclusion pointed out that the simplified LS (s-LS) method is always more efficient, independent of the system conditions, achieving a better performance with a lower complexity than the others heuristics detectors. Associated to this, the deterministic strategy and absence of input parameters made the s-LS algorithm the most appropriate for the MUD problem. (C) 2008 Elsevier GmbH. All rights reserved.

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization

Augmented Lagrangian methods for large-scale optimization usually require efficient algorithms for minimization with box constraints. On the other hand, active-set box-constraint methods employ unconstrained optimization algorithms for minimization inside the faces of the box. Several approaches may be employed for computing internal search directions in the large-scale case. In this paper a minimal-memory quasi-Newton approach with secant preconditioners is proposed, taking into account the structure of Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar scheme. A combined algorithm, that uses the quasi-Newton formula or a truncated-Newton procedure, depending on the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the Cute collection are presented.

Efficient and low cost devices for solar energy conversion: Efficiency and stability of some natural-dye-sensitized solar cells

Dye-sensitized solar cells, named by us Dye-Cells, are one of the most promising devices for solar energy conversion due to their reduced production cost and low environmental impact, especially those sensitized by natural dyes. The efficiency and stability of devices based on natural sensitizers such as mulberry (Morus alba Lam), blueberry (Vaccinium myrtillus Lam), and jaboticaba`s skin (Mirtus cauliflora Mart) were investigated. Dye-Cells prepared with aqueous mulberry extract presented the highest P(max) value (1.6 mW cm(-2)) with J(sc) = 6.14 mA cm(-2) and V(oc) = 0.49 V, Photoelectrochemical parameters of 16 cm(2) active area devices sensitized by mulberry dye were constant for 14 weeks of continuous evaluation. Moreover, the cell remained stable even after 36 weeks with a fairly good efficiency. Therefore, mulberry dye opens up a perspective of commercial feasibility for inexpensive and environmentally friendly Dye-Cells. (C) 2009 Elsevier B.V. All rights reserved.

Apparent digestibility of diets with different concentrations of lysine and energy in piglets with different body weights and post-weaning age

The effects of body weight or age and dietary digestible lysine and metabolizable energy on apparent digestibility of energy and dry matter were evaluated in piglets after weaning. The animals were weaned at 21 days of age and distributed in two groups: 8.68 ± 0.76 kg at 28 days of age (weaned 7 days earlier); and 12.73 ± 0.99 kg at 35 days of age (weaned 14 days earlier). The pigs were allotted in digestibility cages in a completely randomized block design with the following factorial arrangements: 2 × 4 composed of two weight categories and four levels of digestible lysine (1.222; 1.305; 1.390 and 1.497%); and 2 × 3 composed of two weight categories and three levels of metabolizable energy (3,510; 3,700 and 3,830 kcal/kg rations). Digestible lysine was evaluated in six replications and metabolizable energy in eight replications and each animal constituted an experimental unit. Piglets with higher body weight and age were more efficient in nitrogen retention and energetic balance, compared to lighter and younger piglets, particularly those given lower concentration of lysine in the diet. The energy increase favored nitrogen retention by the heavier and older piglets. However, coefficients of dry matter and energy apparent digestibility did not differ among weight categories. Older and heavier piglets were more efficient in nitrogen retention, although this efficacy depended on concentration of the energy in the diet. This better use of protein and energy suggest differences on nutritional requirements.

Gold is not a Faradaic-Efficient Borohydride Oxidation Electrocatalyst: An Online Electrochemical Mass Spectrometry Study

Direct borohydride fuel cells are promising high energy density portable generators. However, their development remains limited by the complexity of the anodic reaction: The borohydride oxidation reaction (BOR) kinetics is slow and occurs at high overvoltages, while it may compete with the heterogeneous hydrolysis of BH(4)(-). Nevertheless, one usually admits that gold is rather inactive toward the heterogeneous hydrolysis of BH(4)(-) and presents some activity regarding the BOR, therefore yielding to the complete eight-electron BOR. In the present paper, by coupling online mass spectrometry to electrochemistry, we in situ monitored the H(2) yield during BOR experiments on sputtered gold electrodes. Our results show non-negligible H(2) generation on Au on the whole BOR potential range (0-0.8 V vs reversible hydrogen electrode), thus revealing that gold cannot be considered as a faradaic-efficient BOR electrocatalyst. We further propose a relevant reaction pathway for the BOR on gold that accounts for these findings.

An efficient heuristic for total flowtime minimisation in no-wait flowshops

In this paper, we address the problem of scheduling jobs in a no-wait flowshop with the objective of minimising the total completion time. This problem is well-known for being nondeterministic polynomial-time hard, and therefore, most contributions to the topic focus on developing algorithms able to obtain good approximate solutions for the problem in a short CPU time. More specifically, there are various constructive heuristics available for the problem [such as the ones by Rajendran and Chaudhuri (Nav Res Logist 37: 695-705, 1990); Bertolissi (J Mater Process Technol 107: 459-465, 2000), Aldowaisan and Allahverdi (Omega 32: 345-352, 2004) and the Chins heuristic by Fink and Voa (Eur J Operat Res 151: 400-414, 2003)], as well as a successful local search procedure (Pilot-1-Chins). We propose a new constructive heuristic based on an analogy with the two-machine problem in order to select the candidate to be appended in the partial schedule. The myopic behaviour of the heuristic is tempered by exploring the neighbourhood of the so-obtained partial schedules. The computational results indicate that the proposed heuristic outperforms existing ones in terms of quality of the solution obtained and equals the performance of the time-consuming Pilot-1-Chins.

New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs. Published by Elsevier Ltd.

Efficient Phosphodiester Hydrolysis by Luminescent Terbium(III) and Europium(III) Complexes

The synthesis and structures of two new isostructural mononuclear [Ln(L)(NO(3))(H(2)O)(3)](NO(3))(2) complexes, with Ln = Tb (complex 1) and Eu (complex 2), which display high activity in the hydrolysis of the substrate 2,4-bis(dinitrophenyl)phosphate, are reported. These complexes displayed catalytic behavior similar to the mononuclear gadolinium complex [Gd(L)(NO(3))(H(2)O)(3)](NO(3))(2) previously reported by us (lnorg. Chem. 2008, 47, 2919-2921); one hydrolysis reaction in two stages where the diesterase and monoesterase activities could be monitored separately, with the first stage dependent on and the second independent of the complex concentration. Through potentiometric studies, electrospray ionization mass spectrometry (ESI-MS) analysis, and determination of the kinetic behaviors of 1 and 2 in acetonitrile/water solution, the species present in solution could be identified and suggested a dinuclear species, with one hydroxo group, as the most prominent catalyst under mild conditions. The complexes show high activity (k(1)= 7 and 18 s(-1) for 1 and 2, respectively) and catalytic efficiency. Complexes 1 and 2 were found to be active toward the cleavage of plasmid DNA, and complete kinetic studies were carried out. Studies with a radical scavenger (dimethylsulfoxide) confirmed the hydrolytic action of 1 and 2 in the cleavage of DNA. Studies on the incubation of distamycin with plasmid DNA suggested that 1 and 2 are regio-specific, interacting with the minor groove of DNA. These complexes displayed luminescent properties. Complex 1 showed higher emission intensity than 2 due to a more efficient energy transfer between triplet and emission levels of terbium (T -> (5)D(4)), along with nonradiative deactivation mechanisms of the excited states of europium via multiphonon decays and the ligand-to-metal charge transfer state. Lifetime measurements of the (5)D(4) and (5)D(0) excited levels for 1 and 2, respectively, indicated the numbers of coordinated water molecules for the complexes.

Efficient bulk-loading on dynamic metric access methods

This paper presents a new technique and two algorithms to bulk-load data into multi-way dynamic metric access methods, based on the covering radius of representative elements employed to organize data in hierarchical data structures. The proposed algorithms are sample-based, and they always build a valid and height-balanced tree. We compare the proposed algorithm with existing ones, showing the behavior to bulk-load data into the Slim-tree metric access method. After having identified the worst case of our first algorithm, we describe adequate counteractions in an elegant way creating the second algorithm. Experiments performed to evaluate their performance show that our bulk-loading methods build trees faster than the sequential insertion method regarding construction time, and that it also significantly improves search performance. (C) 2009 Elsevier B.V. All rights reserved.

PedVis: A Structured, Space-Efficient Technique for Pedigree Visualization

Public genealogical databases are becoming increasingly populated with historical data and records of the current population`s ancestors. As this increasing amount of available information is used to link individuals to their ancestors, the resulting trees become deeper and more dense, which justifies the need for using organized, space-efficient layouts to display the data. Existing layouts are often only able to show a small subset of the data at a time. As a result, it is easy to become lost when navigating through the data or to lose sight of the overall tree structure. On the contrary, leaving space for unknown ancestors allows one to better understand the tree`s structure, but leaving this space becomes expensive and allows fewer generations to be displayed at a time. In this work, we propose that the H-tree based layout be used in genealogical software to display ancestral trees. We will show that this layout presents an increase in the number of displayable generations, provides a nicely arranged, symmetrical, intuitive and organized fractal structure, increases the user`s ability to understand and navigate through the data, and accounts for the visualization requirements necessary for displaying such trees. Finally, user-study results indicate potential for user acceptance of the new layout.

Advanced functionality for radio analysis in the Offline software framework of the Pierre Auger Observatory

The advent of the Auger Engineering Radio Array (AERA) necessitates the development of a powerful framework for the analysis of radio measurements of cosmic ray air showers. As AERA performs ""radio-hybrid"" measurements of air shower radio emission in coincidence with the surface particle detectors and fluorescence telescopes of the Pierre Auger Observatory, the radio analysis functionality had to be incorporated in the existing hybrid analysis solutions for fluorescence and surface detector data. This goal has been achieved in a natural way by extending the existing Auger Offline software framework with radio functionality. In this article, we lay out the design, highlights and features of the radio extension implemented in the Auger Offline framework. Its functionality has achieved a high degree of sophistication and offers advanced features such as vectorial reconstruction of the electric field, advanced signal processing algorithms, a transparent and efficient handling of FFTs, a very detailed simulation of detector effects, and the read-in of multiple data formats including data from various radio simulation codes. The source code of this radio functionality can be made available to interested parties on request. (C) 2011 Elsevier B.V. All rights reserved.

A Time Efficient Optical Model for GATE Simulation of a LYSO Scintillation Matrix Used in PET Applications

A time efficient optical model is proposed for GATE simulation of a LYSO scintillation matrix coupled to a photomultiplier. The purpose is to avoid the excessively long computation time when activating the optical processes in GATE. The usefulness of the model is demonstrated by comparing the simulated and experimental energy spectra obtained with the dual planar head equipment for dosimetry with a positron emission tomograph ( DoPET). The procedure to apply the model is divided in two steps. Firstly, a simplified simulation of a single crystal element of DoPET is used to fit an analytic function that models the optical attenuation inside the crystal. In a second step, the model is employed to calculate the influence of this attenuation in the energy registered by the tomograph. The use of the proposed optical model is around three orders of magnitude faster than a GATE simulation with optical processes enabled. A good agreement was found between the experimental and simulated data using the optical model. The results indicate that optical interactions inside the crystal elements play an important role on the energy resolution and induce a considerable degradation of the spectra information acquired by DoPET. Finally, the same approach employed by the proposed optical model could be useful to simulate a scintillation matrix coupled to a photomultiplier using single or dual readout scheme.

Extending the use of canonical and microcanonical Monte Carlo algorithms to spin models

We describe the canonical and microcanonical Monte Carlo algorithms for different systems that can be described by spin models. Sites of the lattice, chosen at random, interchange their spin values, provided they are different. The canonical ensemble is generated by performing exchanges according to the Metropolis prescription whereas in the microcanonical ensemble, exchanges are performed as long as the total energy remains constant. A systematic finite size analysis of intensive quantities and a comparison with results obtained from distinct ensembles are performed and the quality of results reveal that the present approach may be an useful tool for the study of phase transitions, specially first-order transitions. (C) 2009 Elsevier B.V. All rights reserved.

Energy transfer processes in Yb(3+)-Tm(3+) co-doped sodium alumino-phosphate glasses with improved 1.8 mu m emission

Sodium alumino-phosphate glasses co-doped with Yb(3+) and Tm(3+) ions have been prepared with notably low OH(-) content, and characterized from the viewpoint of their spectroscopic properties. In these glasses, Yb(3+) acts as an efficient sensitizer of excitation energy at 0.98 mu m - which can be provided by high power and low cost diode lasers, and subsequently undergoes non-resonant energy transfer to Tm(3+) ions ((2)F(5/2), (3)H(6) --> (2)F(7/2), (3)H(5)). Through this process, the emitting level (3)F(4) is rapidly populated, generating improved emission at 1.8 mu m ((3)F(4) --> (3)H(6)). In order to guarantee the efficiency of such favorable energy transfer, energy losses via multiphonon decay, Yb-Yb radiative trapping, and non- radiative transfer to OH(-) groups were evaluated, and minimized when possible. The dipole - dipole energy transfer microscopic parameters corresponding to Yb(3+) --> Tm(3+), Yb(3+) --> Yb(3+) and Tm(3+) --> Tm(3+) transfers, calculated by the Forster-Dexter model, are C(Yb-Tm) = 2.9 x 10(-40) cm(6) s(-1), C(Yb-Yb) = 42 x 10(-40) cm(6) s(-1) and C(Tm-Tm) = 43 x 10(-40) cm(6) s(-1), respectively.