Main eigenvalues and (κ, τ)-regular sets

A (κ, τ)-regular set is a subset of the vertices of a graph G, inducing a κ-regular subgraph such that every vertex not in the subset has τ neighbors in it. A main eigenvalue of the adjacency matrix A of a graph G has an eigenvector not orthogonal to the all-one vector j. For graphs with a (κ, τ)-regular set a necessary and sufficient condition for an eigenvalue be non-main is deduced and the main eigenvalues are characterized. These results are applied to the construction of infinite families of bidegreed graphs with two main eigenvalues and the same spectral radius (index) and some relations with strongly regular graphs are obtained. Finally, the determination of (κ, τ)-regular sets is analyzed. © 2009 Elsevier Inc. All rights reserved.

Polyhedral study of mixed integer sets arising from inventory problems

“Branch-and-cut” algorithm is one of the most efficient exact approaches to solve mixed integer programs. This algorithm combines the advantages of a pure branch-and-bound approach and cutting planes scheme. Branch-and-cut algorithm computes the linear programming relaxation of the problem at each node of the search tree which is improved by the use of cuts, i.e. by the inclusion of valid inequalities. It should be taken into account that selection of strongest cuts is crucial for their effective use in branch-and-cut algorithm. In this thesis, we focus on the derivation and use of cutting planes to solve general mixed integer problems, and in particular inventory problems combined with other problems such as distribution, supplier selection, vehicle routing, etc. In order to achieve this goal, we first consider substructures (relaxations) of such problems which are obtained by the coherent loss of information. The polyhedral structure of those simpler mixed integer sets is studied to derive strong valid inequalities. Finally those strong inequalities are included in the cutting plane algorithms to solve the general mixed integer problems. We study three mixed integer sets in this dissertation. The first two mixed integer sets arise as a subproblem of the lot-sizing with supplier selection, the network design and the vendor-managed inventory routing problems. These sets are variants of the well-known single node fixed-charge network set where a binary or integer variable is associated with the node. The third set occurs as a subproblem of mixed integer sets where incompatibility between binary variables is considered. We generate families of valid inequalities for those sets, identify classes of facet-defining inequalities, and discuss the separation problems associated with the inequalities. Then cutting plane frameworks are implemented to solve some mixed integer programs. Preliminary computational experiments are presented in this direction.

Relations between (κ, τ)-regular sets and star complements

Let G be a finite graph with an eigenvalue μ of multiplicity m. A set X of m vertices in G is called a star set for μ in G if μ is not an eigenvalue of the star complement G\X which is the subgraph of G induced by vertices not in X. A vertex subset of a graph is (k ,t)-regular if it induces a k -regular subgraph and every vertex not in the subset has t neighbors in it. We investigate the graphs having a (k,t)-regular set which induces a star complement for some eigenvalue. A survey of known results is provided and new properties for these graphs are deduced. Several particular graphs where these properties stand out are presented as examples.

Determination of (0,2)-regular sets in graphs and applications

In this paper, relevant results about the determination of (k,t)-regular sets, using the main eigenvalues of a graph, are reviewed and some results about the determination of (0,2)-regular sets are introduced. An algorithm for that purpose is also described. As an illustration, this algorithm is applied to the determination of maximum matchings in arbitrary graphs.

Dynamic power- and failure-aware cloud resources allocation for Sets of independent tasks

Cloud computing is increasingly being adopted in different scenarios, like social networking, business applications, scientific experiments, etc. Relying in virtualization technology, the construction of these computing environments targets improvements in the infrastructure, such as power-efficiency and fulfillment of users’ SLA specifications. The methodology usually applied is packing all the virtual machines on the proper physical servers. However, failure occurrences in these networked computing systems can induce substantial negative impact on system performance, deviating the system from ours initial objectives. In this work, we propose adapted algorithms to dynamically map virtual machines to physical hosts, in order to improve cloud infrastructure power-efficiency, with low impact on users’ required performance. Our decision making algorithms leverage proactive fault-tolerance techniques to deal with systems failures, allied with virtual machine technology to share nodes resources in an accurately and controlled manner. The results indicate that our algorithms perform better targeting power-efficiency and SLA fulfillment, in face of cloud infrastructure failures.

Arc exchange systems and renormalization

We exhibit the construction of stable arc exchange systems from the stable laminations of hyperbolic diffeomorphisms. We prove a one-to-one correspondence between (i) Lipshitz conjugacy classes of C(1+H) stable arc exchange systems that are C(1+H) fixed points of renormalization and (ii) Lipshitz conjugacy classes of C(1+H) diffeomorphisms f with hyperbolic basic sets Lambda that admit an invariant measure absolutely continuous with respect to the Hausdorff measure on Lambda. Let HD(s)(Lambda) and HD(u)(Lambda) be, respectively, the Hausdorff dimension of the stable and unstable leaves intersected with the hyperbolic basic set L. If HD(u)(Lambda) = 1, then the Lipschitz conjugacy is, in fact, a C(1+H) conjugacy in (i) and (ii). We prove that if the stable arc exchange system is a C(1+HDs+alpha) fixed point of renormalization with bounded geometry, then the stable arc exchange system is smooth conjugate to an affine stable arc exchange system.

Monoclonal antibodies to murine lipopolysaccharide (LPS)-binding protein (LBP) protect mice from lethal endotoxemia by blocking either the binding of LPS to LBP or the presentation of LPS/LBP complexes to CD14.

Cellular responses to LPS, the major lipid component of the outer membrane of Gram-negative bacteria, are enhanced markedly by the LPS-binding protein (LBP), a plasma protein that transfers LPS to the cell surface CD14 present on cells of the myeloid lineage. LBP has been shown previously to potentiate the host response to LPS. However, experiments performed in mice with a disruption of the LBP gene have yielded discordant results. Whereas one study showed that LBP knockout mice were resistant to endotoxemia, another study did not confirm an important role for LBP in the response of mice challenged in vivo with low doses of LPS. Consequently, we generated rat mAbs to murine LBP to investigate further the contribution of LBP in experimental endotoxemia. Three classes of mAbs were obtained. Class 1 mAbs blocked the binding of LPS to LBP; class 2 mAbs blocked the binding of LPS/LBP complexes to CD14; class 3 mAbs bound LBP but did not suppress LBP activity. In vivo, class 1 and class 2 mAbs suppressed LPS-induced TNF production and protected mice from lethal endotoxemia. These results show that the neutralization of LBP accomplished by blocking either the binding of LPS to LBP or the binding of LPS/LBP complexes to CD14 protects the host from LPS-induced toxicity, confirming that LBP is a critical component of innate immunity.

Blocking VLDL secretion causes hepatic steatosis but does not affect peripheral lipid stores or insulin sensitivity in mice

The liver secretes triglyceride-rich VLDLs, and the triglycerides in these particles are taken up by peripheral tissues, mainly heart, skeletal muscle, and adipose tissue. Blocking hepatic VLDL secretion interferes with the delivery of liver-derived triglycerides to peripheral tissues and results in an accumulation of triglycerides in the liver. However, it is unclear how interfering with hepatic triglyceride secretion affects adiposity, muscle triglyceride stores, and insulin sensitivity. To explore these issues, we examined mice that cannot secrete VLDL [due to the absence of microsomal triglyceride transfer protein (Mttp) in the liver]. These mice exhibit markedly reduced levels of apolipoprotein B-100 in the plasma, along with reduced levels of triglycerides in the plasma. Despite the low plasma triglyceride levels, triglyceride levels in skeletal muscle were unaffected. Adiposity and adipose tissue triglyceride synthesis rates were also normal, and body weight curves were unaffected. Even though the blockade of VLDL secretion caused hepatic steatosis accompanied by increased ceramides and diacylglycerols in the liver, the mice exhibited normal glucose tolerance and were sensitive to insulin at the whole-body level, as judged by hyperinsulinemic euglycemic clamp studies. Normal hepatic glucose production and insulin signaling were also maintained in the fatty liver induced by Mttp deletion. Thus, blocking VLDL secretion causes hepatic steatosis without insulin resistance, and there is little effect on muscle triglyceride stores or adiposity

Generation and characterization of function-blocking anti-ectodysplasin A (EDA) monoclonal antibodies that induce ectodermal dysplasia.

Development of ectodermal appendages, such as hair, teeth, sweat glands, sebaceous glands, and mammary glands, requires the action of the TNF family ligand ectodysplasin A (EDA). Mutations of the X-linked EDA gene cause reduction or absence of many ectodermal appendages and have been identified as a cause of ectodermal dysplasia in humans, mice, dogs, and cattle. We have generated blocking antibodies, raised in Eda-deficient mice, against the conserved, receptor-binding domain of EDA. These antibodies recognize epitopes overlapping the receptor-binding site and prevent EDA from binding and activating EDAR at close to stoichiometric ratios in in vitro binding and activity assays. The antibodies block EDA1 and EDA2 of both mammalian and avian origin and, in vivo, suppress the ability of recombinant Fc-EDA1 to rescue ectodermal dysplasia in Eda-deficient Tabby mice. Moreover, administration of EDA blocking antibodies to pregnant wild type mice induced in developing wild type fetuses a marked and permanent ectodermal dysplasia. These function-blocking anti-EDA antibodies with wide cross-species reactivity will enable study of the developmental and postdevelopmental roles of EDA in a variety of organisms and open the route to therapeutic intervention in conditions in which EDA may be implicated.

Improving the Scalability of Reduct Determination in Rough Sets

Rough Set Data Analysis (RSDA) is a non-invasive data analysis approach that solely relies on the data to find patterns and decision rules. Despite its noninvasive approach and ability to generate human readable rules, classical RSDA has not been successfully used in commercial data mining and rule generating engines. The reason is its scalability. Classical RSDA slows down a great deal with the larger data sets and takes much longer times to generate the rules. This research is aimed to address the issue of scalability in rough sets by improving the performance of the attribute reduction step of the classical RSDA - which is the root cause of its slow performance. We propose to move the entire attribute reduction process into the database. We defined a new schema to store the initial data set. We then defined SOL queries on this new schema to find the attribute reducts correctly and faster than the traditional RSDA approach. We tested our technique on two typical data sets and compared our results with the traditional RSDA approach for attribute reduction. In the end we also highlighted some of the issues with our proposed approach which could lead to future research.

Blocking Top-down awareness of Kanizsa Figures: An ERP Investigation into Bottom-up Processing of Illusory Contours

Neural models of the processing of illusory contour (ICs) diverge from one another in terms of their emphasis on bottom-up versus top-down constituents. The current study uses a dichoptic fusion paradigm to block top-down awareness of ICs in order to examine possible bottom-up effects. Group results indicate that the N170 ERP component is particularly sensitive to ICs at central occipital sites when top-down awareness of the stimulus is permitted. Furthermore, single-subject statistics reveal that the IC N170 ERP effect is highly variable across individuals in terms of timing and topographical spread. The results suggest that the ubiquitous N170 effect to ICs found in the literature depends, at least in part, on participants’ awareness of the stimulus. Therefore a strong bottom-up model of IC processing at the time of the N170 is unlikely.

Ranking Sets of Objects

We provide a survey of the literature on ranking sets of objects. The interpretations of those set rankings include those employed in the theory of choice under complete uncertainty, rankings of opportunity sets, set rankings that appear in matching theory, and the structure of assembly preferences. The survey is prepared for the Handbook of Utility Theory, vol. 2, edited by Salvador Barberà, Peter Hammond, and Christian Seidl, to be published by Kluwer Academic Publishers. The chapter number is provisional.

Von Neumann-Morgenstern Stable Sets in Matching Problems

The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable sets in one-to-one matching problem only if it is a maximal set satisfying the following properties : (a) the core is a subset of the set; (b) the set is a lattice; (c) the set of unmatched agents is identical for any two matchings belonging to the set. Furthermore, a set is a stable set if it is the unique maximal set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.

Pharmacometrics of neuromuscular blocking agents in anesthetized patients and animals : impact of dose and intravascular mixing phase

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal