In this thesis we consider solution approaches for the index tacking problem, in which we aim to reproduces the performance of a market index without purchasing all of the stocks that constitute the index. We solve the problem using three different solution approaches: Mixed Integer Programming (MIP), Genetic Algorithms (GAs), and Ant-colony Optimization (ACO) Algorithm by limiting the number of stocks that can be held. Each index is also assigned with different cardinalities to examine the change to the solution values. All of the solution approaches are tested by considering eight market indices. The smallest data set only consists of 31 stocks whereas the largest data set includes over 2000 stocks. The computational results from the MIP are used as the benchmark to measure the performance of the other solution approaches. The Computational results are presented for different solution approaches and conclusions are given. Finally, we implement post analysis and investigate the best tracking portfolios achieved from the three solution approaches. We summarise the findings of the investigation, and in turn, we further improve some of the algorithms. As the formulations of these problems are mixed-integer linear programs, we use the solver ‘Cplex’ to solve the problems. All of the programming is coded in AMPL.

Decisions regarding the mapping of system-on-chip (SoC) components onto a NoC become more difficult with increasing complexity of system design. These complex systems capable of providing multiple functionalities tend to operate in multiple modes of operation. Modeling the system communication in these multimodes aids in efficient system design. This research provides a heuristic that gives a flexible mapping solution of the multimode system communications onto the NoC topology of choice. The solution specifies the immediate neighbors of the SoC components and the routes taken by all communications in the system. We validate the mapping results with a network-on-chip simulator (NoCSim). This thesis also investigates the cost associated with the interfacing of the components to the NoC. With the goal of reducing communication latency, we examine the packetization strategies in the NoC communication. Three schemes of implementations were analyzed, and the costs in terms of latency, and area were projected through actual synthesis.

Matching is one of the most fundamental algorithmic graph problems. Many variants of matching problems have been studied on different classes of graphs, the one of special interest to us being the Maximum Cardinality Bipartite Matching in Planar Graphs. In this work, we present a novel sparsification based approach for computing maximum/perfect bipartite matching in planar graphs. The overall complexity of our algorithm is O(n^6/5 log² n) where n is the number of vertices in the graph, bettering the O(n^3/2) time achieved independently by Hopcroft-Karp algorithm and by Lipton and Tarjan divide and conquer approach using planar separators. Our algorithm combines the best of both these standard algorithms along with our sparsification technique and rich planar graph properties to achieve the speed up. Our algorithm is not the fastest, with the existence of O(n log³ n) algorithm based on max-flow reduction. / MS / A matching in a graph can be defined as a subset of edges without common vertices. A matching algorithm finds a maximum set of such vertex-disjoint edges. Many real life resource allocation problems can be solved efficiently by modelling them as a matching problem. While many variants of matching problems have been studied on different classes of graphs, the simplest and the most popular among them is the Maximum Cardinality Bipartite Matching problem. Bipartite matching arises in varied applications like matching applicants to job openings, matching ads to user queries, matching threads to tasks in OS scheduler, matching protein sequences based on their structures and so on. In this work, we present an efficient algorithm for computing maximum cardinality bipartite matching in planar graphs. Planar graphs are sparse graphs and have interesting structural properties which allow us to design faster algorithms in planar setting for problems that are otherwise considered hard in arbitrary graphs. We use a new sparsification based approach where we maintain a compact and accurate representation of the original graph with a lesser number of vertices. Our algorithm combines the features of the best known bipartite matching algorithm for an arbitrary graph with the novel sparsification approach to achieve the speedup.

No description available.

Nesta dissertação, abordaremos os dois tipos de infinitos existentes: o infinito potencial e o infinito actual. Apresentaremos algumas situações, exemplos que caracterizam cada um desses dois tipos. Focaremo-nos no infinito actual, com o qual discutiremos alguns dos desafios encontrados na teoria criada por Cantor sobre este assunto. Mostraremos também sua importância e a diferença entre este e o infinito potencial. Com isso, buscamos fazer com que o professor compreenda adequadamente os fundamentos matemáticos necessários para que trabalhe, ensine e motive apropriadamente seus alunos no momento em que o infinito e conjuntos infinitos são discutidos em aula. Desta forma, buscamos esclarecer os termos usados e equívocos comuns cometidos por alunos e também professores, muitas vezes enganados ou confundidos pelo senso comum. / In this dissertation, we will discuss the two types of infinities: the potential infinity and the actual infinity. We will present some situations, examples that characterize each of these two types. We will focus on the actual infinity, with which we will discuss some of the challenges found in the theory created by Cantor on this subject. We will also show its importance and the difference between this and the potential infinity. Thus, we seek to make teachers properly understand the mathematical foundations necessary for them to work, teach and properly motivate their students at the time the infinity and infinite sets are discussed in class. In this way, we seek to clarify the terms used and common mistakes made by students and also teachers, so often misguided or confused by common sense.

The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce. In this study we consider the cardinality constrained multiple knapsack problem. We propose heuristic and optimization procedures that rely on the optimal solutions of the linear programming relaxation problem. Our computational results on the large-sized problem instances have shown the satisfactory performances of our algorithms.

This thesis studies the problem of measuring freedom of choice. It analyzes the concept of freedom of choice, discusses conditions that a measure should satisfy, and introduces a new class of measures that uniquely satisfy ten proposed conditions. The study uses a decision-theoretical model to represent situations of choice and a metric space model to represent differences between options. The first part of the thesis analyzes the concept of freedom of choice. Different conceptions of freedom of choice are categorized into evaluative and non-evaluative, as well as preference-dependent and preference-independent kinds. The main focus is on the three conceptions of freedom of choice as cardinality of choice sets, representativeness of the universal set, and diversity of options, as well as the three conceptions of freedom of rational choice, freedom of eligible choice, and freedom of evaluated choice. The second part discusses the conceptions, together with conditions for a measure and a variety of measures proposed in the literature. The discussion mostly focuses on preference-independent conceptions of freedom of choice, in particular the diversity conception. Different conceptions of diversity are discussed, as well as properties that could affect diversity, such as the cardinality of options, the differences between the options, and the distribution of differences between the options. As a result, the diversity conception is accepted as the proper explication of the concept of freedom of choice. In addition, eight conditions for a measure are accepted. The conditions concern domain-insensitivity, strict monotonicity, no-choice situations, dominance of differences, evenness, symmetry, spread of options, and limited function growth. None of the previously proposed measures satisfy all of these conditions. The third part concerns the construction of a ratio-scale measure that satisfies the accepted conditions. Two conditions are added regarding scale-independence and function growth proportional to cardinality. Lastly, it is shown that only one class of measures satisfy all ten conditions, given an additional assumption that the measures should be analytic functions with non-zero partial derivatives with respect to some function of the differences. These measures are introduced as the Ratio root measures.

Orientador: Francisco de Assis Magalhães Gomes Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T22:50:20Z (GMT). No. of bitstreams: 1 Dias_CarlosHenrique_M.pdf: 2721795 bytes, checksum: 57d6019ecabf33034889a64675ccf707 (MD5) Previous issue date: 2008 / Resumo: Este trabalho tem por finalidade a determinação da fronteira eficiente de investimento através da otimização do modelo de média-variância com restrições de cardinalidade e limite inferior de investimento. Por tratar-se de um problema inteiro e não linear, cuja solução exata é de difícil obtenção, optamos por empregar um algoritmo genético, na linha desenvolvida por Chang et al. [3], que até hoje serve como referência para a determinação da fronteira eficiente de Pareto para problemas de otimização de investimentos. Entretanto, verificamos que o algoritmo proposto por Chang et al. apresenta uma distribuição não uniforme na geração de soluções aleatórias. Para contornar esse problema, introduzimos um novo esquema de geração de cromossomos, baseado na discretização do espaço, que permite a geração de soluções que satisfazem diretamente a restrição de montante total aplicado. Com essa nova abordagem, foi possível definir operadores de seleção, crossover e mutação bastante eficientes. Os resultados obtidos mostram que o novo algoritmo é mais robusto que aquele proposto por Chang et al / Abstract: In this work we consider the problem of determining of the efficient frontier of a portfolio using the mean-variance model subject to a cardinality constrain and to lower bounds on the amount invested in the selected assets. As this nonlinear integer programming problem is hard to solve exactly, we use a genetic algorithm, following the lines described by Chang et al. [3], still considered as a reference in the field. However, as the feasible solutions generated by the algorithm of Chang et al. are not uniformly distributed over the solution set, we introduce a new scheme for defining the chromosomes, based on the discretization of the feasible region, so that the amount invested always sum up to one for every solution obtained by the algorithm. This new approach allows us to define very efficient selection, crossover and mutation procedures. The numerical results obtained so far show that the new method is more robust than the one proposed by Chang et al / Mestrado / Otimização / Mestre em Matemática Aplicada

Nesta dissertação, abordaremos os dois tipos de infinitos existentes: o infinito potencial e o infinito actual. Apresentaremos algumas situações, exemplos que caracterizam cada um desses dois tipos. Focaremo-nos no infinito actual, com o qual discutiremos alguns dos desafios encontrados na teoria criada por Cantor sobre este assunto. Mostraremos também sua importância e a diferença entre este e o infinito potencial. Com isso, buscamos fazer com que o professor compreenda adequadamente os fundamentos matemáticos necessários para que trabalhe, ensine e motive apropriadamente seus alunos no momento em que o infinito e conjuntos infinitos são discutidos em aula. Desta forma, buscamos esclarecer os termos usados e equívocos comuns cometidos por alunos e também professores, muitas vezes enganados ou confundidos pelo senso comum. / In this dissertation, we will discuss the two types of infinities: the potential infinity and the actual infinity. We will present some situations, examples that characterize each of these two types. We will focus on the actual infinity, with which we will discuss some of the challenges found in the theory created by Cantor on this subject. We will also show its importance and the difference between this and the potential infinity. Thus, we seek to make teachers properly understand the mathematical foundations necessary for them to work, teach and properly motivate their students at the time the infinity and infinite sets are discussed in class. In this way, we seek to clarify the terms used and common mistakes made by students and also teachers, so often misguided or confused by common sense.

Dans le cadre de la sélection de meilleurs éléments au sein d’une base de données multidimensionnelle, plusieurs types de requêtes ont été définies. L’opérateur skyline présente l’avantage de ne pas nécessiter la définition d’une fonction de score permettant de classer lesdits éléments. Cependant, la propriété de monotonie que cet opérateur ne présente pas, rend non seulement (i) difficile l’optimisation de ses requêtes dans un contexte multidimensionnel, mais aussi (ii) presque imprévisible la taille du résultat des requêtes. Ce travail se propose, dans un premier temps, d’aborder la question de l’estimation de la taille du résultat d’une requête skyline donnée, en formulant des estimateurs présentant de bonnes propriétés statistiques(sans biais ou convergeant). Ensuite, il fournit deux approches différentes à l’optimisation des requêtes skyline. La première reposant sur un concept classique des bases de données qui est la dépendance fonctionnelle. La seconde se rapprochant des techniques de compression des données. Ces deux techniques trouvent leur place au sein de l’état de l’art comme le confortent les résultats expérimentaux.Nous abordons enfin la question de requêtes skyline au sein de données dynamiques en adaptant l’une de nos solutions précédentes dans cet intérêt. / As part of the selection of the best items in a multidimensional database,several kinds of query were defined. The skyline operator has the advantage of not requiring the definition of a scoring function in order to classify tuples. However, the property of monotony that this operator does not satify, (i) makes difficult to optimize its queries in a multidimensional context, (ii) makes hard to estimate the size of query result. This work proposes, first, to address the question of estimating the size of the result of a given skyline query, formulating estimators with good statistical properties (unbiased or convergent). Then, it provides two different approaches to optimize multidimensional skyline queries. The first leans on a well known database concept: functional dependencies. And the second approach looks like a data compression method. Both algorithms are very interesting as confirm the experimental results. Finally, we address the issue of skyline queries in dynamic data by adapting one of our previous solutions in this goal.