Inference in Polytrees with Sets of Probabilities

Inferences in directed acyclic graphs associated with probability intervals and sets of probabilities are NP-hard, even for polytrees. We propose: 1) an improvement on Tessem’s A/R algorithm for inferences on polytrees associated with probability intervals; 2) a new algorithm for approximate inferences based on local search; 3) branch-and-bound algorithms that combine the previous techniques. The first two algorithms produce complementary approximate solutions, while branch-and-bound procedures can generate either exact or approximate solutions. We report improvements on existing techniques for inference with probability sets and intervals, in some cases reducing computational effort by several orders of magnitude.

Besov spaces and the Laplacian on fractal H-sets

Nesta tese são estudados espaços de Besov de suavidade generalizada em espaços euclidianos, numa classe de fractais designados conjuntos-h e em estruturas abstractas designadas por espaços-h. Foram obtidas caracterizações e propriedades para estes espaços de funções. Em particular, no caso de espaços de Besov em espaços euclidianos, foram obtidas caracterizações por diferenças e por decomposições em átomos não suaves, foi provada uma propriedade de homogeneidade e foram estudados multiplicadores pontuais. Para espaços de Besov em conjuntos-h foi obtida uma caracterização por decomposições em átomos não suaves e foi construído um operador extensão. Com o recurso a cartas, os resultados obtidos para estes espaços de funções em fractais foram aplicados para definir e trabalhar com espaços de Besov de suavidade generalizada em estruturas abstractas. Nesta tese foi também estudado o laplaciano fractal, considerado a actuar em espaços de Besov de suavidade generalizada em domínios que contêm um conjunto-h fractal. Foram obtidos resultados no contexto de teoria espectral para este operador e foi estudado, à custa deste operador, um problema de Dirichlet fractal no contexto de conjuntos-h.

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.

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.

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.

Quelques théorèmes de points critiques basés sur une nouvelle notion d'enlacement

Une nouvelle notion d'enlacement pour les paires d'ensembles $A\subset B$, $P\subset Q$ dans un espace de Hilbert de type $X=Y\oplus Y^{\perp}$ avec $Y$ séparable, appellée $\tau$-enlacement, est définie. Le modèle pour cette définition est la généralisation de l'enlacement homotopique et de l'enlacement au sens de Benci-Rabinowitz faite par Frigon. En utilisant la théorie du degré développée dans un article de Kryszewski et Szulkin, plusieurs exemples de paires $\tau$-enlacées sont donnés. Un lemme de déformation est établi et utilisé conjointement à la notion de $\tau$-enlacement pour prouver un théorème d'existence de point critique pour une certaine classe de fonctionnelles sur $X$. De plus, une caractérisation de type minimax de la valeur critique correspondante est donnée. Comme corollaire de ce théorème, des conditions sont énoncées sous lesquelles l'existence de deux points critiques distincts est garantie. Deux autres théorèmes de point critiques sont démontrés dont l'un généralise le théorème principal de l'article de Kryszewski et Szulkin mentionné ci-haut.

Anomaly Detection Using System Call Sequence Sets.

This paper discusses our research in developing a generalized and systematic method for anomaly detection. The key ideas are to represent normal program behaviour using system call frequencies and to incorporate probabilistic techniques for classification to detect anomalies and intrusions. Using experiments on the sendmail system call data, we demonstrate that concise and accurate classifiers can be constructed to detect anomalies. An overview of the approach that we have implemented is provided.

Computing median and antimedian sets in median graphs

The median (antimedian) set of a profile π = (u1, . . . , uk) of vertices of a graphG is the set of vertices x that minimize (maximize) the remoteness i d(x,ui ). Two algorithms for median graphs G of complexity O(nidim(G)) are designed, where n is the order and idim(G) the isometric dimension of G. The first algorithm computes median sets of profiles and will be in practice often faster than the other algorithm which in addition computes antimedian sets and remoteness functions and works in all partial cubes

Prediction of Key Symptoms of Learning Disabilities in School-Age Children Using Rough Sets

This paper highlights the prediction of learning disabilities (LD) in school-age children using rough set theory (RST) with an emphasis on application of data mining. In rough sets, data analysis start from a data table called an information system, which contains data about objects of interest, characterized in terms of attributes. These attributes consist of the properties of learning disabilities. By finding the relationship between these attributes, the redundant attributes can be eliminated and core attributes determined. Also, rule mining is performed in rough sets using the algorithm LEM1. The prediction of LD is accurately done by using Rosetta, the rough set tool kit for analysis of data. The result obtained from this study is compared with the output of a similar study conducted by us using Support Vector Machine (SVM) with Sequential Minimal Optimisation (SMO) algorithm. It is found that, using the concepts of reduct and global covering, we can easily predict the learning disabilities in children