Ranking a set of candidates or items from pair-wise comparisons is a fundamental problem that arises in many settings such as elections, recommendation systems, sports team rankings, document rankings and so on. Indeed it is well known in the psychology literature that when a large number of items are to be ranked, it is easier for humans to give pair-wise comparisons as opposed to complete rankings. The problem of ranking from pair-wise comparisons has been studied in multiple communities such as machine learning, operations research, linear algebra, statistics etc., and several algorithms (both classic and recent) have been proposed. However, it is not well under-stood under what conditions these different algorithms perform well. In this thesis, we aim to fill this fundamental gap, by elucidating precise conditions under which different algorithms perform well, as well as giving new algorithms that provably perform well under broader conditions. In particular, we consider a natural statistical model wherein for every pair of items (i; j), there is a probability Pij such that each time items i and j are compared, item j beats item i with probability Pij . Such models, which we summarize through a matrix containing all these pair-wise probabilities, have been used explicitly or implicitly in much previous work in the area; we refer to the resulting matrix as the pair-wise preference matrix, and elucidate clearly the crucial role it plays in determining the performance of various algorithms. In the first part of the thesis, we consider a natural generative model where all pairs of items can be sampled and where the underlying preferences are assumed to be acyclic. Under this setting, we elucidate the conditions on the pair-wise preference matrix under which popular algorithms such as matrix Borda, spectral ranking, least squares and maximum likelihood under a Bradley-Terry-Luce (BTL) model produce optimal rankings that minimize the pair-wise disagreement error. Specifically, we derive explicit sample complexity bounds for each of these algorithms to output an optimal ranking under interesting subclasses of the class of all acyclic pair-wise preference matrices. We show that none of these popular algorithms is guaranteed to produce optimal rankings for all acyclic preference matrices. We then pro-pose a novel support vector machine based rank aggregation algorithm that provably does so. In the second part of the thesis, we consider the setting where preferences may contain cycles. Here, finding a ranking that minimizes the pairwise disagreement error is in general NP-hard. However, even in the presence of cycles, one may wish to rank 'good' items ahead of the rest. We develop a framework for this setting using notions of winners based on tournament solution concepts from social choice theory. We first show that none of the existing algorithms are guaranteed to rank winners ahead of the rest for popular tournament solution based winners such as top cycle, Copeland set, Markov set etc. We propose three algorithms - matrix Copeland, unweighted Markov and parametric Markov - which provably rank winners at the top for these popular tournament solutions. In addition to ranking winners at the top, we show that the rankings output by the matrix Copeland and the parametric Markov algorithms also minimize the pair-wise disagreement error for certain classes of acyclic preference matrices. Finally, in the third part of the thesis, we consider the setting where the number of items to be ranked is large and it is impractical to obtain comparisons among all pairs. Here, one samples a small set of pairs uniformly at random and compares each pair a fixed number of times; in particular, the goal is to come up with good algorithms that sample comparisons among only O(nlog(n)) item pairs (where n is the number of items). Unlike existing results for such settings, where one either assumes a noisy permutation model (under which there is a true underlying ranking and the outcome of every comparison differs from the true ranking with some fixed probability) or assumes a BTL or Thurstone model, we develop a general algorithmic framework based on ideas from matrix completion, termed low-rank pair-wise ranking, which provably produces an good ranking by comparing only O(nlog(n)) pairs, O(log(n)) times each, not only for popular classes of models such as BTL and Thurstone, but also for much more general classes of models wherein a suitable transform of the pair-wise probabilities leads to a low-rank matrix; this subsumes the guarantees of many previous algorithms in this setting. Overall, our results help to understand at a fundamental level the statistical properties of various algorithms for the problem of ranking from pair-wise comparisons, and under various natural settings, lead to novel algorithms with improved statistical guarantees compared to existing algorithms for this problem.

Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté G = (V,E). Chaque sommet de V représente un capteur et une arête e = {u, v} dans E indique une transmission directe possible entre deux capteurs u et v. Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des noeuds "dominants" qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes. Cette étude est consacrée aux ensembles indépendants faiblement connexes. Un indépendant S ⊂ V est dit faiblement connexe si le graphe GS = (V, [S, V \S]) est connexe, où [S, V \S] est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \S. Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires. Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes. Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté G est connexe. Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP). Nous décrivons également un algorithme d’énumération exact de complexité O∗(1.4655|V |) pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés. Nous formulons ensuite le MWCISP comme un programme linéaire en nombres entiers. Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque G est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales. Nous introduisons des inégalités valides notamment les contraintes dites de multibord. Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés. / In this work, we focus on a topology for Wireless Sensor Networks (WSN). A wireless sensor network can be modeled as an undirected graph G = (V,E). Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = (V, [S, V \S]) is connected, where [S, V \S] is the set of edges with exactly one end in S. A sensor network topology based on weakly connected sets is partition into three groups, slaves, masters and bridges. The first performs the measurements, the second gathers the collected data and the later provides the inter-group communications. We first give some properties of this combinatorial structure when the undirected graph G is connected. Then we provide complexity results for the problem of finding the minimum weakly connected independent set problem (MWCISP). We also describe an exact enumeration algorithm of complexity O∗(1.4655|V |) (for the (MWCISP)). Numerical tests of this exact procedure are also presented. We then present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristical separation algorithms for them. Finally, we develop a branch-and-cut algorithm and test it on two classes of graphs.

We construct and investigate random geometric structures that are based on a homogeneous Poisson point process. We investigate the random Vietoris-Rips complex constructed as the clique complex of the well known gilbert graph as an infinite random simplicial complex and prove that every realizable finite sub-complex will occur infinitely many times almost sure as isolated complex and also in the case of percolations connected to the unique giant component. Similar results are derived for the Cech complex. We derive limit theorems for the f-vector of the Vietoris-Rips complex on the unit cube centered at the origin and provide a central limit theorem and a Poisson limit theorem based on the model parameters. Finally we investigate random polytopes that are given as convex hulls of a Poisson point process in a smooth convex body. We establish a central limit theorem for certain linear combinations of intrinsic volumes. A multivariate limit theorem involving the sequence of intrinsic volumes and the number of i-dimensional faces is derived. We derive the asymptotic normality of the oracle estimator of minimal variance for estimation of the volume of a convex body.

Contrary to popular belief, we can’t all be winners. Suppose 6 people compete in a chess tournament in which all pairs of players compete directly and no ties are allowed; i.e., 6 people compete in a ‘round robin tournament’. Each player is assigned a ‘score’, namely the number of games they won, and the ‘score sequence’ of the tournament is a list of the players’ scores. Determining whether a given potential score sequence actually is a score sequence proves to be difficult. For instance, (0, 0, 3, 3, 3, 6) is not feasible because two players cannot both have score 0. Neither is the sequence (1, 1, 1, 4, 4, 4) because the sum of the scores is 16, but only 15 games are played among 6 players. This so called ‘tournament score sequence problem’ (TSSP) was solved in 1953 by the mathematical sociologist H. G. Landau. His work inspired the investigation of round robin tournaments as directed graphs. We study a modification in which the TSSP is cast as a system of inequalities whose solutions form a polytope η-dimensional space. This relaxation allows us to investigate the possibility of fractional scores. If, in a ‘round-robin’-ish tournament, Players A and B play each other 3 times, and Player A wins 2 of the 3 games, we can record this interaction as a 2/3 score for Player A and a 1/3 score for Player B. This generalization greatly impacts the nature of possible score sequences. We will also entertain an interpretation of these fractional scores as probabilities predicting the outcome of a true round robin tournament. The intersection of digraph theory, polyhedral combinatorics, and linear programming is a relatively new branch of graph theory. These results pioneer research in this field.

No description available.

Unmanned aerial vehicles are becoming more popular in today’s society, which results in the rise of laws intended to maintain safety. To abide by these, while allowing the technology to expand, functioning path-planning algorithms are required.This also includes having methods for detecting and managing obstacles. This project aims to improve an existing path-planning algorithm that is based on A* and implemented in Python.The solution consisted of using functions for finding polytopeintersection,as well as optimizing the collision avoidance and the search algorithm. In addition to that, realistic constraints were implemented on the generated trajectory in order to reflect real-life limitations. The results demonstrated that the paths were always feasible, with respect to input and position constraints. The program’s computation time was also reduced up to 89% of the original run-time. There is, however, still room for improvement since the original code generated a shorter path for the three scenarios it was created for. On the other hand,the improved algorithm could handle a new scenario, which the original code failed to do. / Obemannade flygfarkoster blir alltmer vanliga i dagens samhälle, vilket resulterar i uppkomsten av nya lagar ämnade åt att upprätthålla säkerhet. För att förhålla sig till dessa, samtidigt som teknologin tillåts expandera, krävs fungerande vägplaneringsalgoritmer. Där ingår det även att ha metoder för att upptäcka och hantera hinder. Detta projekt syftar till att förbättra en befintlig vägplaneringsalgoritm som är baserad på A* och implenterad i Python. Lösningsmetoden bestod av att använda inbyggda Python-funktioner ämnade åt att finna skärningar mellan polytoper, samt optimera kollisionshantering och sökalgoritmen. Dessutom infördes realistiska krav på den framställda vägen i syfte om att reflektera verlighetens begränsningar. Resultatet visade att vägarna alltid var genomförbara, med avseende på inmatningsoch positionsrelaterade villkor. Programmets beräkningstid hade även reducerats upptill 89% av den ursprungliga körtiden. Det finns dock utrymme för förbättringar då den ursprungliga koden generar en kortare väg för de tre scenarion den tillverkades för. Däremot kinde den förbättrade algoritmen hantera ett nytt scenario, en ursprungliga koden misslyckades med. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed. We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time. We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results. After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances. Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them. Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case. ------------------------------------------------ Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits. Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes. Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3. Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème. Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas.

Submitted by Adalberto Zanatta Neder Lazarini null (adalberto.lazarini@yahoo.com) on 2017-02-02T20:05:36Z No. of bitstreams: 1 Dissertação Adalberto - Final.pdf: 1297717 bytes, checksum: 4cea64840d9e8f7f2841989ef7ea349a (MD5) / Approved for entry into archive by LUIZA DE MENEZES ROMANETTO (luizamenezes@reitoria.unesp.br) on 2017-02-06T17:12:01Z (GMT) No. of bitstreams: 1 lazarini_azn_me_ilha.pdf: 1297717 bytes, checksum: 4cea64840d9e8f7f2841989ef7ea349a (MD5) / Made available in DSpace on 2017-02-06T17:12:01Z (GMT). No. of bitstreams: 1 lazarini_azn_me_ilha.pdf: 1297717 bytes, checksum: 4cea64840d9e8f7f2841989ef7ea349a (MD5) Previous issue date: 2017-01-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho são feitas análises sobre quando as condições de existência dos teoremas apresentados por (GUEDES, 2015), que propõem condições necessárias e suficientes para a estabilidade de sistemas não lineares de tempo contínuo descritos através de modelos fuzzy Takagi-Sugeno (TS), que transformam sistemas não lineares em um conjunto convexo de sistemas lineares a partir de regras se-então, baseadas em Funções de Lyapunov Fuzzy (FLF), são satisfeitas. Primeiramente, são analisados os casos particulares de 3 e 4 modelos locais. Logo após, são tratados casos genéricos, com quantidades de regras tanto pares quanto ímpares, identificando quando as condições impostas pelos teoremas citados são satisfeitas. Para os casos nos quais as condições não são satisfeitas, é proposto também um algoritmo para obtenção do “pior caso” possível, varrendo todas as possibilidades que o sistema apresenta. Este algoritmo oferece condições necessárias e suficientes para o problema e também pode ser utilizado quando as condições exigidas pelos dois teoremas apresentados em (GUEDES, 2015) são satisfeitas. Por fim, são analisadas as contribuições do uso do algoritmo, onde são considerados parâmetros como número de LMIs, número de variáveis matriciais simétricas nxn simétricas utilizadas na resolução das LMIs e tempo computacionalmente necessário. / In this work,the required conditions for the theorems presented by(GUEDES,2015), which propose necessary and sufficient conditions for the stability of continuous-time nonlinear systems described by Takagi-Sugeno (TS) fuzzy models based on Lyapunov fuzzy functions (LFF), are analysed. First of all, the cases with 3 and 4 local models are considered. After that, generic cases are studied, with odd or even number os rules, identifying when the conditions imposed by these theorem shold. If the conditions are not satisfied, an algorithm is proposed as way of finding the “worst case scenario” for the system, considering all possible options. This algorithm offers necessary and sufficient conditions for solving this problem and also can be used when the conditions for the application of the theorems presented in(GUEDES,2015) hold. Finally,the algorithm’s contributions are analyzed, considering parameters such as number of LMIs,number of symmetric matricial variables used on solving the LMIs and computational time.

Ce mémoire est consacré à trois modèles classiques de géométrie aléatoire : les mosaïques, les enveloppes convexes et le modèle booléen. Dans la première partie, on étudie les mosaïques poissonniennes d'hyperplans isotropes et plus particulièrement leur zéro-cellule qui est un polyèdre convexe aléatoire de l'espace euclidien. Deux cas particuliers de zéro-cellules sont la cellule typique de Poisson-Voronoi et la cellule de Crofton. On donne une formule explicite pour la loi du nombre de côtés d'une zéro-cellule en dimension deux. On s'intéresse au comportement asymptotique de cette loi et on fait le lien avec le problème de Sylvester des points en position convexe. On décrit ensuite la loi du rayon circonscrit ainsi que le comportement asymptotique du polyèdre à grand rayon inscrit au moyen de théorèmes limites. De cette manière et aussi par l'utilisation de la fréquence fondamentale, on apporte des précisions à l'énoncé de la conjecture de D. G. Kendall. La seconde partie a pour objet les enveloppes convexes de processus ponctuels de Poisson isotropes dans la boule-unité. On établit un résultat de type grandes déviations pour le nombre de sommets. On montre ensuite la convergence de la frontière de l'enveloppe après changement d'échelle et on en déduit des résultats de valeurs extrêmes, estimations de variance, théorèmes centraux limites et principes d'invariance pour certaines caractéristiques. Dans la troisième partie, on s'intéresse enfin aux modèles de recouvrement de type booléen de l'espace euclidien. Dans un premier travail, on applique une variante du modèle sans interpénétration des objets à la modélisation d'un phénomène de fissuration. On étudie ensuite la convergence de la composante connexe de l'origine d'un modèle booléen vers la cellule de Crofton en dimension deux. On s'intéresse enfin à la fonction de visibilité de cette composante connexe pour laquelle on obtient une estimée de la queue de distribution et des résultats de valeurs extrêmes.

La méthode d'homogénéisation en calcul à la rupture permet de calculer les propriétés de résistance à l'échelle macroscopique d'un matériau hétérogène périodique (matériaux composites, sols renforcés) à partir de la solution d'un problème de calcul à la rupture défini sur la période de base. Une méthode numérique spécifique destinée à résoudre un tel problème est mise au point. Elle est fondée sur la mise en oeuvre de l'approche cinématique du calcul à la rupture et conduit : 1) à la recherche du minimum d'une fonction convexe d'un nombre fini de paramètres scalaires pour laquelle un algorithme de résolution est proposé. 2) à une évaluation par l'extérieur du convexe de résistance macroscopique qui se révèle d'autant plus précise que le nombre de paramètres de minimisation est élevé. On procède à de nombreuses applications de cette méthode à des problèmes de "contrainte plane" (plaques renforcées ou perforées chargées dans leur plan) et son extension prometteuse à des problèmes en "déformation plane" est esquissée.