A linear optimization technique for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is NP 2 -complete. In this paper we develop a tool, called theWeight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply theWeight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.

A parameter-free approach for solving combinatorial optimization problems through biased randomization of efficient heuristics

This paper discusses the use of probabilistic or randomized algorithms for solving combinatorial optimization problems. Our approach employs non-uniform probability distributions to add a biased random behavior to classical heuristics so a large set of alternative good solutions can be quickly obtained in a natural way and without complex conguration processes. This procedure is especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods, both of exact and approximate nature, may fail to reach their full potential. The results obtained are promising enough to suggest that randomizing classical heuristics is a powerful method that can be successfully applied in a variety of cases.

On the stability of the optimal value and the optimal set in optimization problems

The paper develops a stability theory for the optimal value and the optimal set mapping of optimization problems posed in a Banach space. The problems considered in this paper have an arbitrary number of inequality constraints involving lower semicontinuous (not necessarily convex) functions and one closed abstract constraint set. The considered perturbations lead to problems of the same type as the nominal one (with the same space of variables and the same number of constraints), where the abstract constraint set can also be perturbed. The spaces of functions involved in the problems (objective and constraints) are equipped with the metric of the uniform convergence on the bounded sets, meanwhile in the space of closed sets we consider, coherently, the Attouch-Wets topology. The paper examines, in a unified way, the lower and upper semicontinuity of the optimal value function, and the closedness, lower and upper semicontinuity (in the sense of Berge) of the optimal set mapping. This paper can be seen as a second part of the stability theory presented in [17], where we studied the stability of the feasible set mapping (completed here with the analysis of the Lipschitz-like property).

Artificial Snow Optimization in Winter Sport Destinations Using a Multi-agent Simulation

This paper presents the Juste-Neige system for predicting the snow height on the ski runs of a resort using a multi-agent simulation software. Its aim is to facilitate snow cover management in order to i) reduce the production cost of artificial snow and to improve the profit margin for the companies managing the ski resorts; and ii) to reduce the water and energy consumption, and thus to reduce the environmental impact, by producing only the snow needed for a good skiing experience. The software provides maps with the predicted snow heights for up to 13 days. On these maps, the areas most exposed to snow erosion are highlighted. The software proceeds in three steps: i) interpolation of snow height measurements with a neural network; ii) local meteorological forecasts for every ski resort; iii) simulation of the impact caused by skiers using a multi-agent system. The software has been evaluated in the Swiss ski resort of Verbier and provides useful predictions.

Lymphatic Filariasis in Brazilian Urban Area (Maceió, Alagoas)

A cross-sectional survey conducted among evening students was used to determine the prevalence of Wuchereria bancrofti infection in Maceió, capital of the State of Alagoas, northeast Brazil. A single thick-blood smear was used, being collected between 10 p.m. and 12 a.m. From a total of 29,551 students enrolled at evening elementary schools in the 33 city sectors, 16,569 (56.4%) were random selected for inclusion in the study. From those, 10,857 (65.5%) were interviewed and examined and 73 (0.7%) were found to have microfilaraemia. Autochthonous W. bancrofti carriers live in 10 of the 33 city sectors, suggesting a focal distribution. Moreover, 84% of infections were diagnosed among 29% of all students examined, inhabiting three contiguous sectors at the city central area, presenting infection rates up to 5.3%. Students living in city sectors with prevalence of microfilariae carriers greater than 1% were found to have a higher risk for infection when compared to students from the rest of the town [Relative Odds (RO) 12.8, 95% CI 6.7 - 25.1]. Eleven positive individuals from non endemic areas were living in Maceió for more than 10 years; time of residence in the area was a major risk factor for infection among students not born in the region (p<0.01). Regarding sex, male students presented a higher proportion of positive (RO 1.7, 95% CI 1.1 - 2.9).

Application of detection probabilities to the design of amphibian monitoring programs in temporary ponds

Failure to detect a species in an area where it is present is a major source of error in biological surveys. We assessed whether it is possible to optimize single-visit biological monitoring surveys of highly dynamic freshwater ecosystems by framing them a priori within a particular period of time. Alternatively, we also searched for the optimal number of visits and when they should be conducted. We developed single-species occupancy models to estimate the monthly probability of detection of pond-breeding amphibians during a four-year monitoring program. Our results revealed that detection probability was species-specific and changed among sampling visits within a breeding season and also among breeding seasons. Thereby, the optimization of biological surveys with minimal survey effort (a single visit) is not feasible as it proves impossible to select a priori an adequate sampling period that remains robust across years. Alternatively, a two-survey combination at the beginning of the sampling season yielded optimal results and constituted an acceptable compromise between sampling efficacy and survey effort. Our study provides evidence of the variability and uncertainty that likely affects the efficacy of monitoring surveys, highlighting the need of repeated sampling in both ecological studies and conservation management.

Extremity and eye lens doses in interventional radiology and cardiology procedures: first results of the ORAMED project.

The main objective of WP1 of the ORAMED (Optimization of RAdiation protection for MEDical staff) project is to obtain a set of standardised data on extremity and eye lens doses for staff in interventional radiology (IR) and cardiology (IC) and to optimise staff protection. A coordinated measurement program in different hospitals in Europe will help towards this direction. This study aims at analysing the first results of the measurement campaign performed in IR and IC procedures in 34 European hospitals. The highest doses were found for pacemakers, renal angioplasties and embolisations. Left finger and wrist seem to receive the highest extremity doses, while the highest eye lens doses are measured during embolisations. Finally, it was concluded that it is difficult to find a general correlation between kerma area product and extremity or eye lens doses.

Chronic carriers of hepatitis B surface antigen in an endemic area for schistosomiasis mansoni in Brazil

Data on the association of schistosomiasis and hepatitis B in field-based studies are scarce. Two areas have been selected for this study: i) Queixadinha, endemic for schistosomiasis, with a population of 693 individuals, and ii) Capão, a control non-endemic area, with 515 inhabitants. Sera of all individuals in both areas were tested for hepatitis B infection, yearly, from 1994 to 1997. In the first area hepatitis B was found in 32.1% of children up to one year old and reached a peak of 68.7% in the age range of 15 to 19 years. In the control area the prevalence of hepatitis B was under 5% up to 19 years of age and the highest prevalence was observed in adults over 45. HBsAg was detected in 9.4% of the individuals living in the endemic area for schistosomiasis and in 1.4% of the controls (OR=4.98; 95%CI=3.7-6.7). The index of chronicity of HBsAg was not statistically different in the studied areas (8.1% x 7.3%; OR = 1.09; 95%CI= 0.42-3.03), nor was it different for people with and without schistosomiasis in Queixadinha (8.7% x 7.0%). We conclude that the Schistosoma mansoni infection has not altered the course of hepatitis B in the studied area.

A comparative study on IgG-ELISA, IgM-IFT and Kato-Katz methods for epidemiological purposes in a low endemic area for schistosomiasis

The high sensitivity and the possibility of automation of the enzyme-linked-immunosorbent-assay (ELISA) has indicated this technique as one of the most useful serological test for epidemiological studies. In the present study, an ELISA for detection of IgG antibodies against adult worm antigens (IgG-ELISA) was investigated for epidemiological purposes, in a rural area of the municipality of Itariri (São Paulo, Brazil). Blood on filter paper (1,180 samples) from about 650 schoolchildren were submitted to ELISA and the data compared to the results of the parasitological method of Kato-Katz and also to the IgM-IFT (immunofluorescence test for IgM antibodies to gut associated antigens). The prevalence rates respectively of 8.5%, 43.0%, and 56.2% by the Kato-Katz, IgG-ELISA, and IgM-IFT methods suggest the poor sensitivity of the parasitological method for detection of Schistosoma mansoni eggs in individuals with low worm burden, situation commonly observed in low endemic areas. These results can partially explain the poor degree of agreement between the IgG-ELISA and the Kato-Katz, as suggested by the Kappa index of 0.170. Otherwise, the Kappa index of 0.675 showed substantial agreement between the two serological tests. Some discrepancy of results between the two serological techniques must be better investigated.

Comparative Analysis by Polymerase Chain Reaction Amplified Minicircles of Kinetoplast DNA of a Stable Strain of Trypanosoma cruzi from São Felipe, Bahia, its Clones and Subclones: Possibility of Predominance of a Principal Clone in this Area

Molecular characterization of one stable strain of Trypanosoma cruzi, the 21 SF, representative of the pattern of strains isolated from the endemic area of São Felipe, State of Bahia, Brazil, maintained for 15 years in laboratory by serial passages in mice and classified as biodeme Type II and zymodeme 2 has been investigated. The kinetoplast DNA (kDNA) of parental strain, 5 clones and 14 subclones were analyzed. Schizodeme was established by comparative study of the fragments obtained from digestion of the 330-bp fragments amplified by polymerase chain reaction (PCR) from the variable regions of the minicicles, and digested by restriction endonucleases Rsa I and Hinf I. Our results show a high percentual of similarity between the restriction fragment lenght polymorphism (RFLP) for the parental strain and its clones and among these individual clones and their subclones at a level of 80 to 100%.This homology indicates a predominance of the same "principal clone" in the 21SF strain and confirms the homogeneity previously observed at biological and isozymic analysis. These results suggest the possibility that the T. cruzi strains with similar biological and isoenzymic patterns, circulating in this endemic area, are representative of one dominant clone. The presence of "principal clones" could be responsible for a predominant tropism of the parasites for specific organs and tissues and this could contribute to the pattern of clinico-pathological manifestations of Chagas's disease in one geographical area.

Distribution of Sandflies (Diptera:Psychodidae) on Tree-trunks in a Non-flooded Area of the Ducke Forest Reserve, Manaus, AM, Brazil

Sandflies were collected in the base of tree-trunks in the seasons of high and least rainfall in the Ducke Forest Reserve, near Manaus in the State of Amazonas. Lutzomyia umbratilis was the most abundant sandfly species. Caryocar villosum, Chrysophyllum amazonicum, Dinizia excelsa, Eschweilera atropetiolata and Parkia multijuga were the tree species on which most sandflies were collected and relative abundance were related to trunk characteristics. Seasonal patterns of sandfly distribution in the forest were observed.