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.

Same wording, distinct concepts? Testing differences between expectancies and motives in a mediation model of alcohol outcomes.

Per definition, alcohol expectancies (after alcohol I expect X), and drinking motives (I drink to achieve X) are conceptually distinct constructs. Theorists have argued that motives mediate the association between expectancies and drinking outcomes. Yet, given the use of different instruments, do these constructs remain distinct when assessment items are matched? The present study tested to what extent motives mediated the link between expectancies and alcohol outcomes when identical items were used, first as expectancies and then as motives. A linear structural equation model was estimated based on a national representative sample of 5,779 alcohol-using students in Switzerland (mean age = 15.2 years). The results showed that expectancies explained up to 38% of the variance in motives. Together with motives, they explained up to 48% of the variance in alcohol outcomes (volume, 5+ drinking, and problems). In 10 of 12 outcomes, there was a significant mediated effect that was often higher than the direct expectancy effect. For coping, the expectancy effect was close to zero, indicating the strongest form of mediation. In only one case (conformity and 5+ drinking), there was a direct expectancy effect but no mediation. To conclude, the study demonstrates that motives are distinct from expectancies even when identical items are used. Motives are more proximally related to different alcohol outcomes, often mediating the effects of expectancies. Consequently, the effectiveness of interventions, particularly those aimed at coping drinkers, should be improved through a shift in focus from expectancies to drinking motives.

The effect of patient, provider and financing regulations on the intensity of ambulatory physical therapy episodes : a multilevel analysis based on routinely available data

Background: Many studies have found considerable variations in the resource intensity of physical therapy episodes. Although they have identified several patient-and provider-related factors, few studies have examined their relative explanatory power. We sought to quantify the contribution of patients and providers to these differences and examine how effective Swiss regulations are (nine-session ceiling per prescription and bonus for first treatments). Methods: Our sample consisted of 87,866 first physical therapy episodes performed by 3,365 physiotherapists based on referrals by 6,131 physicians. We modeled the number of visits per episode using a multilevel log linear regression with crossed random effects for physiotherapists and physicians and with fixed effects for cantons. The three-level explanatory variables were patient, physiotherapist and physician characteristics. Results: The median number of sessions was nine (interquartile range 6-13). Physical therapy use increased with age, women, higher health care costs, lower deductibles, surgery and specific conditions. Use rose with the share of nine-session episodes among physiotherapists or physicians, but fell with the share of new treatments. Geographical area had no influence. Most of the variance was explained at the patient level, but the available factors explained only 4% thereof. Physiotherapists and physicians explained only 6% and 5% respectively of the variance, although the available factors explained most of this variance. Regulations were the most powerful factors. Conclusion: Against the backdrop of abundant physical therapy supply, Swiss financial regulations did not restrict utilization. Given that patient-related factors explained most of the variance, this group should be subject to closer scrutiny. Moreover, further research is needed on the determinants of patient demand.

A multilevel approach to understanding circadian rhythmicity : social and sleep-dependent effects in ants and mice

Résumé françaisLa majorité des organismes vivants sont soumis à l'alternance du jour et de la nuit, conséquence de la rotation de la terre autour de son axe. Ils ont développé un système interne de mesure du temps, appelé horloge circadienne, leur permettant de s'adapter et de synchroniser leur comportement et leur physiologie aux cycles de lumière. Cette dernière est considérée comme étant le signal majeur entraînant l'horloge interne et. par conséquent, les rythmes journaliers d'éveil et de sommeil. Outre sa régulation circadienne, le sommeil est contrôlé par un processus homéostatique qui détermine son besoin. La contribution de ces deux processus dans le fonctionnement cellulaire du cerveau n'a pas encore été investiguée. La mesure de l'amplitude ainsi que de la prévalence des ondes delta de l'EEG (activité delta) constitue un index très fiable du besoin de sommeil. Il a été démontré que cette activité est génétiquement déterminée et associée à un locus de trait quantitatif situé sur le chromosome 13 de la souris.Grâce à des expériences de privation de sommeil et d'analyses de transcriptome du cerveau dans trois souches de souris présentant diverses réponses à la privation de sommeil, nous avons trouvé que Homerla, localisé dans la région d'intérêt du chromosome 13, est le meilleur marqueur du besoin de sommeil. Homerla est impliqué dans la récupération de l'hyperactivité neuronale induite par le glutamate, grâce à son effet tampon sur le calcium intracellulaire. Une fonction fondamentale du sommeil pourrait donc être de protéger le cerveau et de lui permettre de récupérer après une hyperactivité neuronale imposée par une veille prolongée.De plus, nous avons montré que 2032 transcrits sont exprimés rythmiqueraent dans le cerveau de la souris, parmi lesquels seulement 391 le restent après que les animaux aient été privés de sommeil à différents moments au cours des 24 heures. Cette observation montre clairement que la plupart des changements rythmiques au niveau du transcriptome dépendent du sommeil et non de l'horloge circadienne et souligne ainsi l'importance du sommeil dans la physiologie des mammifères.La plupart des expériences concernant les rythmes circadiens ont été réalisées sur des individus isolés en négligeant l'effet du contexte social sur les comportements circadiens. Les espèces sociales, telles que les fourmis, se caractérisent par une division du travail où une répartition des tâches s'effectue entre ses membres. De plus, certaines d'entre elles doivent être pratiquées en continu comme les soins au couvain tandis que d'autres requièrent une activité rythmique comme le fourragement. Ainsi la fourmi est un excellent modèle pour l'étude de 1 influence du contexte social sur les rythmes circadiens.A ces fins, nous avons décidé d'étudier les rythmes circadiens chez une espèce de fourmi Camponotus fellah et de caractériser au niveau moléculaire son horloge circadienne. Nous avons ainsi développé un système vidéo permettant de suivre l'activité locomotrice de tous les individus d'une colonie. Nos résultats montrent que, bien que la plupart des fourmis soient arythmiques à l'intérieur de la colonie, elles développent d'amples rythmes d'activité en isolation. De plus, ces rythmes disparaissent presque aussitôt que la fourmi est réintroduite dans la colonie. Cette rythmicité observée en isolation semble être générée par l'horloge circadienne car elle persiste en condition constante (obscurité totale). Nous avons ensuite regardé si cette apparente arythmie observée dans la colonie résultait d'un effet masquant des interactions sociales sur les rythmes circadiens d'activité. Nos résultats suggèrent que l'horloge interne est fonctionnelle dans la colonie mais que l'expression de ses rythmes au niveau comportemental est inhibée par les interactions sociales. Les analyses moléculaires du statut de l'horloge dans différents contextes sociaux sont actuellement en cours. Le contexte social semble donc un déterminant majeur du comportement circadien chez la fourmi.AbstractAlmost all living organisms on earth are subjected to the alternance of day and night re-sulting from the rotation of the earth around its axis. They have evolved with an internal timing system, termed the circadian clock, enabling them to adapt and synchronize their behavior and physiology to the daily changes in light and related environmental parame¬ters. Light is thought to be the major cue entraining the circadian clock and consequently the rhythms of rest/activity. In addition to its circadian dependent timing, sleep is reg¬ulated by a homeostatic process that determines its need. The contribution of these two processes in the cellular functioning of the brain has not yet been considered. A highly reliable index of the homeostatic process of sleep is the measure of the amplitude and prevalence of the EEG delta waves (delta activity). It has been shown that sleep need, measured by delta activity, is genetically determined and associated with a Quantitative Trait Locus (QTL) located on the mouse chromosome 13. By using sleep deprivation and brain transcriptome profiling in three inbred mouse strains showing different responses to sleep loss, we found that Homerla, localized within this QTL region is the best transcrip¬tional marker of sleep need. Interestingly Homerla is primarily involved in the recovery from glutamate-induced neuronal hyperactivity by its buffering effect on intracellular cal¬cium. A fundamental function of sleep may therefore reside in the protection and recovery of the brain from a neuronal hyperactivity imposed by prolonged wakefulness.Moreover, time course gene expression experiments showed that 2032 brain tran¬scripts present a rhythmic variation, but only 391 of those remain rhythmic when mice are sleep deprived at four time points around the clock. This finding clearly suggests that most changes in gene transcription over the day are sleep-wake dependent rather than clock dependent and underlines the importance of sleep in mammalian physiology.In the second part of this PhD, I was interested in the social influence on circadian behavior. Most experiments done in the circadian field have been performed on isolated individuals and have therefore ignored the effect of the social context on circadian behav-ior. Eusocial insect species such as ants are characterized by a division of labor: colony tasks are distributed among individuals, some of them requiring continuous activity such as nursing or rhythmic ones such as foraging. Thus ants represent a suitable model to study the influence of the social context on the circadian clock and its output rhythms.The aim of this part was to address the effect of social context on circadian rhythms in the ant species Camponotus fellah and to characterize its circadian clock at the molecu¬lar level. We therefore developed a video tracking system to follow the locomotor activity of all individuals in a colony. Our results show that most ants are arrhythmic within the colony, but develop, when subjected to social isolation, strong rhythms of activity that intriguingly disappear when individuals are reintroduced into the colony. The rhythmicity observed in isolated ants seems to be driven by the circadian clock as it persists under constant conditions (complete darkness). We then tested whether the apparent arrhyth- micity in the colony stemmed from a masking effect of social interactions on circadian rhythms. Indeed, we found that circadian clocks of ants in the colony are functional but their expression at the behavioral level is inhibited by social interactions. The molecular assessment of the circadian clock functional state in the different social context is still under investigation. Our results suggest that social context is a major determinant of circadian behavior in ants.

Steady-state brain glucose transport kinetics re-evaluated with a four-state conformational model.

Glucose supply from blood to brain occurs through facilitative transporter proteins. A near linear relation between brain and plasma glucose has been experimentally determined and described by a reversible model of enzyme kinetics. A conformational four-state exchange model accounting for trans-acceleration and asymmetry of the carrier was included in a recently developed multi-compartmental model of glucose transport. Based on this model, we demonstrate that brain glucose (G(brain)) as function of plasma glucose (G(plasma)) can be described by a single analytical equation namely comprising three kinetic compartments: blood, endothelial cells and brain. Transport was described by four parameters: apparent half saturation constant K(t), apparent maximum rate constant T(max), glucose consumption rate CMR(glc), and the iso-inhibition constant K(ii) that suggests G(brain) as inhibitor of the isomerisation of the unloaded carrier. Previous published data, where G(brain) was quantified as a function of plasma glucose by either biochemical methods or NMR spectroscopy, were used to determine the aforementioned kinetic parameters. Glucose transport was characterized by K(t) ranging from 1.5 to 3.5 mM, T(max)/CMR(glc) from 4.6 to 5.6, and K(ii) from 51 to 149 mM. It was noteworthy that K(t) was on the order of a few mM, as previously determined from the reversible model. The conformational four-state exchange model of glucose transport into the brain includes both efflux and transport inhibition by G(brain), predicting that G(brain) eventually approaches a maximum concentration. However, since K(ii) largely exceeds G(plasma), iso-inhibition is unlikely to be of substantial importance for plasma glucose below 25 mM. As a consequence, the reversible model can account for most experimental observations under euglycaemia and moderate cases of hypo- and hyperglycaemia.

An alternative method for dating unknown tephras based on a segmented regression model

In CoDaWork’05, we presented an application of discriminant function analysis (DFA) to 4 differentcompositional datasets and modelled the first canonical variable using a segmented regression modelsolely based on an observation about the scatter plots. In this paper, multiple linear regressions areapplied to different datasets to confirm the validity of our proposed model. In addition to dating theunknown tephras by calibration as discussed previously, another method of mapping the unknown tephrasinto samples of the reference set or missing samples in between consecutive reference samples isproposed. The application of these methodologies is demonstrated with both simulated and real datasets.This new proposed methodology provides an alternative, more acceptable approach for geologists as theirfocus is on mapping the unknown tephra with relevant eruptive events rather than estimating the age ofunknown tephra.Kew words: Tephrochronology; Segmented regression

Drivers of human resource management competences development in Brazilian multinational subsidiaries: a multilevel research

This article aims to verify the factors associated with the development of human resource management (HRM) competences in foreign subsidiaries of Brazilian multinationals. These competences are essential in that they allow foreign units to adopt HRM practices that are consistent with the countries or markets in which they operate. A multilevel research was conducted, involving headquarters and subsidiaries of major Brazilian companies; the empirical analysis employed hierarchical linear modelling. Despite the recurrent debate on global standardisation versus local adaptation, it was identified that the integration of international HRM policies (addressing simultaneously global guidelines and local response) may stimulate competences development. In addition, interaction in external networks in the host country may enhance the development of HRM competences in the subsidiaries. However, specific cultural factors of the company may inhibit development activity in units abroad.

Assembling genes from predicted exons in linear time with dynamic programming

In a number of programs for gene structure prediction in higher eukaryotic genomic sequences, exon prediction is decoupled from gene assembly: a large pool of candidate exons is predicted and scored from features located in the query DNA sequence, and candidate genes are assembled from such a pool as sequences of nonoverlapping frame-compatible exons. Genes are scored as a function of the scores of the assembled exons, and the highest scoring candidate gene is assumed to be the most likely gene encoded by the query DNA sequence. Considering additive gene scoring functions, currently available algorithms to determine such a highest scoring candidate gene run in time proportional to the square of the number of predicted exons. Here, we present an algorithm whose running time grows only linearly with the size of the set of predicted exons. Polynomial algorithms rely on the fact that, while scanning the set of predicted exons, the highest scoring gene ending in a given exon can be obtained by appending the exon to the highest scoring among the highest scoring genes ending at each compatible preceding exon. The algorithm here relies on the simple fact that such highest scoring gene can be stored and updated. This requires scanning the set of predicted exons simultaneously by increasing acceptor and donor position. On the other hand, the algorithm described here does not assume an underlying gene structure model. Indeed, the definition of valid gene structures is externally defined in the so-called Gene Model. The Gene Model specifies simply which gene features are allowed immediately upstream which other gene features in valid gene structures. This allows for great flexibility in formulating the gene identification problem. In particular it allows for multiple-gene two-strand predictions and for considering gene features other than coding exons (such as promoter elements) in valid gene structures.

How does the body-scale model affect back-calculated growth: the example of arctic charr Salvelinus alpinus (L.) of Lake Geneva (Switzerland)

When back-calculating fish length from scale measurements, the choice of the body-scale relationship is a fundamental step. Using data from the arctic charrSalvelinus alpinus (L.) of Lake Geneva (Switzerland) we show the need for a curvilinear model, on both statistical and biological grounds. From several 2-parameters models, the log-linear relationship appears to provide the best fit. A 3-parameters, Bertalanffy model did not improve the fit. We show moreover that using the proportional model would lead to important misinterpretations of the data.

A New Model for Designing a Product Line Using TURF Analysis

This paper introduces the approach of using TURF analysis to design a product line through a binary linear programming model. This improves the efficiency of the search for the solution to the problem compared to the algorithms that have been used to date. Furthermore, the proposed technique enables the model to be improved in order to overcome the main drawbacks presented by TURF analysis in practice.

A validated assay for measuring doxorubicin in biological fluids and tissues in an isolated lung perfusion model: matrix effect and heparin interference strongly influence doxorubicin measurements.

Doxorubicin is an antineoplasic agent active against sarcoma pulmonary metastasis, but its clinical use is hampered by its myelotoxicity and its cumulative cardiotoxicity, when administered systemically. This limitation may be circumvented using the isolated lung perfusion (ILP) approach, wherein a therapeutic agent is infused locoregionally after vascular isolation of the lung. The influence of the mode of infusion (anterograde (AG): through the pulmonary artery (PA); retrograde (RG): through the pulmonary vein (PV)) on doxorubicin pharmacokinetics and lung distribution was unknown. Therefore, a simple, rapid and sensitive high-performance liquid chromatography method has been developed to quantify doxorubicin in four different biological matrices (infusion effluent, serum, tissues with low or high levels of doxorubicin). The related compound daunorubicin was used as internal standard (I.S.). Following a single-step protein precipitation of 500 microl samples with 250 microl acetone and 50 microl zinc sulfate 70% aqueous solution, the obtained supernatant was evaporated to dryness at 60 degrees C for exactly 45 min under a stream of nitrogen and the solid residue was solubilized in 200 microl of purified water. A 100 microl-volume was subjected to HPLC analysis onto a Nucleosil 100-5 microm C18 AB column equipped with a guard column (Nucleosil 100-5 microm C(6)H(5) (phenyl) end-capped) using a gradient elution of acetonitrile and 1-heptanesulfonic acid 0.2% pH 4: 15/85 at 0 min-->50/50 at 20 min-->100/0 at 22 min-->15/85 at 24 min-->15/85 at 26 min, delivered at 1 ml/min. The analytes were detected by fluorescence detection with excitation and emission wavelength set at 480 and 550 nm, respectively. The calibration curves were linear over the range of 2-1000 ng/ml for effluent and plasma matrices, and 0.1 microg/g-750 microg/g for tissues matrices. The method is precise with inter-day and intra-day relative standard deviation within 0.5 and 6.7% and accurate with inter-day and intra-day deviations between -5.4 and +7.7%. The in vitro stability in all matrices and in processed samples has been studied at -80 degrees C for 1 month, and at 4 degrees C for 48 h, respectively. During initial studies, heparin used as anticoagulant was found to profoundly influence the measurements of doxorubicin in effluents collected from animals under ILP. Moreover, the strong matrix effect observed with tissues samples indicate that it is mandatory to prepare doxorubicin calibration standard samples in biological matrices which would reflect at best the composition of samples to be analyzed. This method was successfully applied in animal studies for the analysis of effluent, serum and tissue samples collected from pigs and rats undergoing ILP.

Importância da Programação Linear na Determinação de Informações de Gestão - Caso Moave, Sa

A Investigação Operacional vem demonstrando ser uma valiosa ferramenta de gestão nos dias de hoje em que se vive num mercado cada vez mais competitivo. Através da Programação Linear pode-se reproduzir matematicamente um problema de maximização dos resultados ou minimização dos custos de produção com o propósito de auxiliar os gestores na tomada de decisão. A Programação Linear é um método matemático em que a função objectivo e as restrições assumem características lineares, com diversas aplicações no controlo de gestão, envolvendo normalmente problemas de utilização dos recursos disponíveis sujeitos a limitações impostas pelo processo produtivo ou pelo mercado. O objectivo geral deste trabalho é o de propor um modelo de Programação Linear para a programação ou produção e alocação de recursos necessários. Optimizar uma quantidade física designada função objectivo, tendo em conta um conjunto de condicionalismos endógenas às actividades em gestão. O objectivo crucial é dispor um modelo de apoio à gestão contribuindo assim para afectação eficiente de recursos escassos à disposição da unidade económica. Com o trabalho desenvolvido ficou patente a importância da abordagem quantitativa como recurso imprescindível de apoio ao processo de decisão. The operational research has proven to be a valuable management tool today we live in an increasingly competitive market. Through Linear Programming can be mathematically reproduce a problem of maximizing performance or minimizing production costs in order to assist managers in decision making. The Linear Programming is a mathematical method in which the objective function and constraints are linear features, with several applications in the control of management, usually involving problems of resource use are available subject to limitations imposed by the production process or the market. The overall objective of this work is to propose a Linear Programming model for scheduling or production and allocation of necessary resources. Optimizing a physical quantity called the objective function, given a set of endogenous constraints on management thus contributing to efficient allocation of scarce resources available to the economic unit. With the work has demonstrated the importance of the quantitative approach as essential resource to support the decision process.

Fusion of data sets in multivariate linear regression with errors-in-variables

We consider the application of normal theory methods to the estimation and testing of a general type of multivariate regressionmodels with errors--in--variables, in the case where various data setsare merged into a single analysis and the observable variables deviatepossibly from normality. The various samples to be merged can differ on the set of observable variables available. We show that there is a convenient way to parameterize the model so that, despite the possiblenon--normality of the data, normal--theory methods yield correct inferencesfor the parameters of interest and for the goodness--of--fit test. Thetheory described encompasses both the functional and structural modelcases, and can be implemented using standard software for structuralequations models, such as LISREL, EQS, LISCOMP, among others. An illustration with Monte Carlo data is presented.

A new compact linear programming formulation for choice network revenue management

The choice network revenue management model incorporates customer purchase behavioras a function of the offered products, and is the appropriate model for airline and hotel networkrevenue management, dynamic sales of bundles, and dynamic assortment optimization.The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalencerelaxation of the dynamic program, called the choice deterministic linear program(CDLP) is usually used to generate dyamic controls. Recently, a compact linear programmingformulation of this linear program was given for the multi-segment multinomial-logit (MNL)model of customer choice with non-overlapping consideration sets. Our objective is to obtaina tighter bound than this formulation while retaining the appealing properties of a compactlinear programming representation. To this end, it is natural to consider the affine relaxationof the dynamic program. We first show that the affine relaxation is NP-complete even for asingle-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive a newcompact linear program that approximates the dynamic programming value function betterthan CDLP, provably between the CDLP value and the affine relaxation, and often comingclose to the latter in our numerical experiments. When the segment consideration sets overlap,we show that some strong equalities called product cuts developed for the CDLP remain validfor our new formulation. Finally we perform extensive numerical comparisons on the variousbounds to evaluate their performance.