In this paper we establish the existence and partial regularity of a (d-2)-dimensional edge-length minimizing polyhedron in [Special characters omitted.] . The minimizer is a generalized convex polytope of volume one which is the limit of a minimizing sequence of polytopes converging in the Hausdorff metric. We show that the (d-2)-dimensional edge-length ζ d -2 is lower-semicontinuous under this sequential convergence. Here the edge set of the limit generalized polytope is a closed subset of the boundary whose complement in the boundary consists of countably many relatively open planar regions.

We generalize bistellar operations (often called flips) on simplicial manifolds to a notion of general flips on PL-spheres. We provide methods for computing the cd-index of these general flips, which is the change in the cd-index of any sphere to which the flip is applied. We provide formulas and relations among flips in certain classes, paying special attention to the classic case of bistellar flips. We also consider questions of "flip-connecticity", that is, we show that any two polytopes in certain classes can be connected via a sequence of flips in an appropriate class.

This thesis is a contribution to determine the absolute irreducibility of polynomials via their Newton polytopes. For any field F / a polynomial f in F[x1, x2,..., xk] can be associated with a polytope, called its Newton polytope. If the polynomial f has integrally indecomposable Newton polytope, in the sense of Minkowski sum, then it is absolutely irreducible over F / i.e. irreducible over every algebraic extension of F. We present some new results giving integrally indecomposable classes of polytopes. Consequently, we have some new criteria giving infinitely many types of absolutely irreducible polynomials over arbitrary fields.

Thesis (Ph. D.)--University of Alberta, 2010. / Title from pdf file main screen (viewed on July 13, 2010). A thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Mathematics, Department of Mathematical and Statistical Sciences, University of Alberta. Includes bibliographical references.

Orientador: Sandro Rigo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T08:17:12Z (GMT). No. of bitstreams: 1 Vieira_CristiannoMartins_M.pdf: 1981128 bytes, checksum: 5af9a00808029ad96cd8d02e569b1cda (MD5) Previous issue date: 2010 / Resumo: Embora muitos programas possuam uma forma regular de paralelismo, que pode ser expressa em termos de laços paralelos, muitos exemplos importantes não a possuem. Loop skewing é uma transformação que remodela o espaço de iteração dos laços para que seja possível expressar o paralelismo implícito através de laços paralelos. Como consequência da complexidade em se modificar o espaço de iteração dos laços, e de possíveis problemas causados por transformações deste tipo - como o possível aumento na taxa de miss em caches -, no geral, elas não são largamente utilizadas. Neste projeto, implementamos a transformação loop skewing sobre o compilador da linguagem C presente no GCC (GNU Compiler Collection), de forma a permitir a assistência pelo programador. Utilizamos a ferramenta Graphite como base para a implementação da otimização, apenas representando-a como uma transformação afim sobre um objeto matemático multidimensional chamado polítopo. Mostramos, através de um estudo detalhado sobre o modelo matemático denominado modelo politópico, que laços com estruturas específicas - perfeitamente aninhados, com limites e acesso á memória descritos por funções afins - poderiam ser representados como polítopos, e que transformações aplicadas a estes seriam espelhadas no código gerado a partir desses polítopos. Dessa forma, qualquer transformação que possa ser estruturada como uma transformação afim sobre um polítopo, poderá ser implementada. Mostramos, ainda, durante a análise de desempenho, que transformações deste tipo são viáveis e, apesar de algumas limitações impostas pela infraestrutura do GCC, aumentam relativamente o desempenho das aplicações compiladas com ela - obtivemos um ganho máximo de aproximadamente 115% para o uso de quatro threads em uma das aplicações executadas. Verificamos o impacto do uso de programas já paralelizados manualmente sobre a plataforma, e obtivemos um ganho máximo de 11% nesses casos, mostrando que ainda aplicações paralelizadas podem conter paralelismo implícito / Abstract: Although many programs present a regular form of parallelism, which can be expressed as parallel loops, many important examples do not. Loop skewing is a transformation that reorganizes the iteration space of loops to make it possible to expose the implicit parallelism through parallel loops. In general, as a consequence of the complexity in modifying the iteration space of loops, and possible problems caused by such changes - such as the possibility of increasing the miss rate in caches -, they are not widely used. In this work, the loop skewing transformation was implemented on GCC's C compiler (GNU Compiler Collection), allowing programmer's assistance. Graphite provides us a basis for implementation of the optimization, just representing it as an a_ne transformation on a multidimensional mathematical object called polytope. We show, through a detailed study about the mathematical model called polytope model, that for a very restricted loop structure - perfectly nested, with limits and memory accesses described by a_ne functions - could be represented as polytopes, and transformations applied to these would be carried by the code generated from these polytope. Thus, any transformation that could be structured as an a_ne transformation on a polytope, could be added. We also show, by means of performance analysis, that this type of transformation is feasible and, despite some limitations imposed by the still under development GCC's infrastructure for auto-parallelization, fairly increases the performance of some applications compiled with it - we achived a maximum of about 115% using four threads with one of the applications. We also veriéd the impact of using manually parallelized programs on this platform, and achieved a maximum gain of 11% in these cases, showing that even parallel applications may have implicit parallelism / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

The convex hull of a sample is used to approximate the support of the underlying distribution. This approximation has many practical implications in real life. For example, approximating the boundary of a finite set is used by many authors in environmental studies and medical research. To approximate the functionals of convex hulls, asymptotic theory plays a crucial role. Unfortunately, the asymptotic results are mostly very complicated. To address this complication, we suggest a consistent bootstrapping scheme for certain cases. Our resampling technique is used for both semi-parametric and non-parametric cases. Let X1,X2,...,Xn be a sequence of i.i.d. random points uniformly distributed on an unknown convex set. Our bootstrapping scheme relies on resampling uniformly from the convex hull of X1,X2,...,Xn. In this thesis, we study the asymptotic consistency of certain functionals of convex hulls. In particular, we apply our bootstrapping technique to the Hausdorff distance between the actual convex set and its estimator. We also provide a conjecture for the application of our bootstrapping scheme to Gaussian polytopes. Moreover, some other relevant consistency results for the regular bootstrap are developed.

The problem of computing the minimum distance between two convex hulls has applications to many areas including robotics, computer graphics and path planning. Moreover, determining the minimum distance between two convex hulls plays a significant role in support vector machines (SVM). In this study, a new algorithm for finding the minimum distance between two convex hulls is proposed and investigated. A convergence of the algorithm is proved and applicability of the algorithm to support vector machines is demostrated. The performance of the new algorithm is compared with the performance of one of the most popular algorithms, the sequential minimal optimization (SMO) method. The new algorithm is simple to understand, easy to implement, and can be more efficient than the SMO method for many SVM problems.

Nous introduisons d'abord la classe des graphes $k$-dégénérés qui est souvent utilisée pour modéliser des grands graphes épars issus du monde réel. Nous proposons de nouveaux algorithmes d'énumération pour ces graphes. En particulier, nous construisons un algorithme énumérant tous les cycles simples de tailles fixés dans ces graphes, en temps optimal.Nous proposons aussi un algorithme dont la complexité dépend de la taille de la solution pour le problème d'énumération des cliques maximales de ces graphes. Dans un second temps nous considérons les graphes en tant que systèmes distribués et nous nous intéressons à des questions liées à la notion de couplage lorsqu’aucune supposition n’est faite sur l'état initial du système, qui peut donc être correct ou incorrect. Dans ce cadre nous proposons un algorithme retournant une deux tiers approximation du couplage maximum.Nous proposons aussi un algorithme retournant un couplage maximal quand les communications sont restreintes de telle manière à simuler le paradigme du passage de message. Le troisième objet d'étude n'est pas directement lié à l'algorithmique de graphe, bien que quelques techniques classiques de ce domaine soient utilisées pour obtenir certains de nos résultats.Nous introduisons et étudions certaines familles de polytopes, appelées Zonotopes Primitifs, qui peuvent être décrits comme la somme de Minkowski de vecteurs primitifs. Nous prouvons certaines propriétés combinatoires de ces polytopes et illustrons la connexion avec le plus grand diamètre possible de l'enveloppe convexe de points à coordonnées entières à valeurs dans$[k]$, en dimension $d$. Dans un second temps,nous étudions des paramètres de petites instances de Zonotopes Primitifs, tels que leur nombre de sommets, entre autres. / We start by studying the class of $k$-degenerate graphs which are often used to model sparse real-world graphs. We focus one numeration questions for these graphs. That is,we try and provide algorithms which must output, without duplication, all the occurrences of some input subgraph. We investigate the questions of finding all cycles of some givensize and all maximal cliques in the graph. Ourtwo contributions are a worst-case output sizeoptimal algorithm for fixed-size cycleenumeration and an output sensitive algorithmfor maximal clique enumeration for this restricted class of graphs. In a second part weconsider graphs in a distributed manner. Weinvestigate questions related to finding matchings of the network, when no assumptionis made on the initial state of the system. Thesealgorithms are often referred to as selfstabilizing.Our two main contributions are analgorithm returning an approximation of themaximum matching and a new algorithm formaximal matching when communication simulates message passing. Finally, weintroduce and investigate some special families of polytopes, namely primitive zonotopes,which can be described as the Minkowski sumof short primitive vectors. We highlight connections with the largest possible diameter ofthe convex hull of a set of points in dimension d whose coordinates are integers between 0 and k.Our main contributions are new lower bounds for this diameter question as well as descriptions of small instances of these objects.

In this thesis, we propose and study discrete, multi-period extensions of classical packing problems, a fundamental class of models in combinatorial optimization. Those extensions fall under the general name of incremental packing problems. In such models, we are given an added time component and different capacity constraints for each time. Over time, capacities are weakly increasing as resources increase, allowing more items to be selected. Once an item is selected, it cannot be removed in future times. The goal is to maximize some (possibly also time-dependent) objective function under such packing constraints. In Chapter 2, we study the generalized incremental knapsack problem, a multi-period extension to the classical knapsack problem. We present a policy that reduces the generalized incremental knapsack problem to sequentially solving multiple classical knapsack problems, for which many efficient algorithms are known. We call such an algorithm a single-time algorithm. We prove that this algorithm gives a (0.17 - ⋲)-approximation for the generalized incremental knapsack problem. Moreover, we show that the algorithm is very efficient in practice. On randomly generated instances of the generalized incremental knapsack problem, it returns near optimal solutions and runs much faster compared to Gurobi solving the problem using the standard integer programming formulation. In Chapter 3, we present additional approximation algorithms for the generalized incremental knapsack problem. We first give a polynomial-time (½-⋲)-approximation, improving upon the approximation ratio given in Chapter 2. This result is based on a new reformulation of the generalized incremental knapsack problem as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys-Tardos algorithm for the generalized assignment problem. Using the same sequencing reformulation, combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we give a quasi-polynomial time approximation scheme for the problem, thus ruling out the possibility that the generalized incremental knapsack problem is APX-hard under widely-believed complexity assumptions. In Chapter 4, we first turn our attention to the submodular monotone all-or-nothing incremental knapsack problem (IK-AoN), a special case of the submodular monotone function subject to a knapsack constraint extended to a multi-period setting. We show that each instance of IK-AoN can be reduced to a linear version of the problem. In particular, using a known PTAS for the linear version from literature as a subroutine, this implies that IK-AoN admits a PTAS. Next, we study special cases of the generalized incremental knapsack problem and provide improved approximation schemes for these special cases. In Chapter 5, we give a polynomial-time (¼-⋲)-approximation in expectation for the incremental generalized assignment problem, a multi-period extension of the generalized assignment problem. To develop this result, similar to the reformulation from Chapter 3, we reformulate the incremental generalized assignment problem as a multi-machine sequencing problem. Following the reformulation, we show that the (½-⋲)-approximation for the generalized incremental knapsack problem, combined with further randomized rounding techniques, can be leveraged to give a constant factor approximation in expectation for the incremental generalized assignment problem. In Chapter 6, we turn our attention to the incremental knapsack polytope. First, we extend one direction of Balas's characterization of 0/1-facets of the knapsack polytope to the incremental knapsack polytope. Starting from extended cover inequalities valid for the knapsack polytope, we show how to strengthen them to define facets for the incremental knapsack polytope. In particular, we prove that under the same conditions for which these inequalities define facets for the knapsack polytope, following our strengthening procedure, the resulting inequalities define facets for the incremental knapsack polytope. Then, as there are up to exponentially many such inequalities, we give separation algorithms for this class of inequalities.

Cette thèse porte sur la reconstruction de formes linéaires sur l'anneau des polynômes dans le cas multivarié et ses applications. Nous proposons des outils théoriques et algorithmiques permettant de résoudre des problèmes liés aux moments : la reconstruction de polytopes convexes à partir de leurs moments et la recherche de cubatures. L'algorithme numérique proposé pour reconstruire des polytopes utilise des méthodes numériques utilisées précédemment pour le cas des polygones, ainsi que les identités de Brion reliant moments directionnels et sommets projetés. Un polyèdre à 57 sommets - la coupe d'un diamant - est ainsi reconstruit. Pour la recherche de cubatures, nous adaptons la méthode de Prony univariée en une méthode multivariée à l'aide des opérateurs de Hankel. Un problème de complétion de matrices est aussi résolu grâce au théorème d'extension plate de Curto-Fialkow. Nous expliquons ainsi la recherche de cubatures à l'aide des matrices de moments, connue dans la littérature. La symétrie, qui est ici un élément naturel, réduit la complexité algorithmique. Nous prouvons qu'une diagonalisation par blocs des matrices concernées est alors possible. De ces blocs et à l'aide de la matrice de multiplicités d'un groupe fini, des conditions nécessaires à l'existence de cubatures sont obtenues. Pour une mesure, un degré et un nombre de nœuds donnés, notre algorithme certifie tout d'abord l'existence de cubatures et ensuite calcule ses poids et nœuds. De nouvelles cubatures ont ainsi été trouvées : soit en complétant celles connues pour une mesure et un degré donnés, soit en ajoutant des cubatures de degrés supérieurs pour une mesure donnée. / This thesis deals with the reconstruction of linear forms on the polynomial ring and its applications. We propose theoretical and algorithmic tools to solve multivariate moment problems: the reconstruction of convex polytopes from their moments (shape-from-moments) and the search for cubatures. The numerical algorithm we propose to reconstruct polytopes uses numerical methods previously known in the case of polygons, and also Brion's identities that relate directional moments and projected vertices. A polyhedron with 57 vertices – a diamond cut – is thus reconstructed. Concerning the search for cubatures, we adapt the univariate Prony's method into a multivariate method thanks to Hankel operators. A matrix completion problem is then solved with a basis-free version of Curto-Fialkow's flat extension theorem. We explain thus the moment matrix approach to cubatures, known in the litterature. Symmetry is here a natural ingredient and reduces the algorithmic complexity. We show that a block diagonalisation of the involved matrices is possible. Those blocs and the matrix of multiplicities of a finite group provide necessary conditions on the existence of cubatures. Given a measure, a degree and a number of nodes, our algorithm first certify the existence of cubatures and then compute the weights and nodes. New cubatures have been found: either by completing the ones known for a given measure and degree, or by adding cubatures with a higher degree for a given measure.