Combinatorial Algorithms and Optimization - Laboratoire Interdisciplinaire des Sciences du Numérique Accéder directement au contenu
Thèse Année : 2017

Combinatorial Algorithms and Optimization

Algorithmes combinatoires et optimisation

George Manoussakis
  • Fonction : Auteur
  • PersonId : 1027583

Résumé

We investigate three main questions in this thesis. The first two are related to graph algorithmic problems. Given general or restricted classes of graphs, we design algorithms in order to achieve some given result. We start by introducing the class of k-degenerate graphs which are often used to model sparse real world graphs. We then focus on enumeration questions for these graphs. That is, we try and provide algorithms which must output, without duplication, all the occurrences of some input subgraph with some given properties. In the scope of this thesis, we investigate the questions of finding all subgraphs which have the property to be cycles of some given size and all subgraphs which have the property to be maximal cliques in the input sparse graph. Our two main contributions related to these problems are a worst-case output size optimal algorithm for fixed-size cycle enumeration and an output sensitive algorithm for maximal clique enumeration for this restricted class of graphs. The second main object that we study is also related to graph algorithmic questions, although in a very dierent setup. We want to consider graphs in a distributed manner. Each vertex or node has some computing power and can communicate with its neighbors. Nodes must then cooperate in order to solve a global problem. In this context, we mainly investigate questions related to finding matchings (a set of edges of the graph with no common end vertices) assuming any possible initialization (correct or incorrect) of the system. These algorithms are often referred to as self-stabilizing since no assumption is made on the initial state of the system. In this context, our two main contributions are the rst polynomial time self-stabilizing algorithm returning a 2/3-approximation of the maximum matching and a new self-stabilizing algorithm for maximal matching when communication is restricted in such a way as to simulate the message passing paradigm. Our third object of study is not related to graph algorithms, although some classical techniques are borrowed from that field to achieve some of our results. We introduce and investigate some special families of polytopes, namely primitive zonotopes, which can be described as the Minkowski sum of short primitive vectors. We prove some of their combinatorial properties and highlight connections with the largest possible diameter of the 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 polytopes.
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.
Fichier principal
Vignette du fichier
mainvdef.pdf (3.16 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

tel-01835110 , version 1 (23-07-2018)

Identifiants

  • HAL Id : tel-01835110 , version 1

Citer

George Manoussakis. Combinatorial Algorithms and Optimization. Computer Science [cs]. Paris-Sud XI, 2017. English. ⟨NNT : ⟩. ⟨tel-01835110⟩
370 Consultations
101 Téléchargements

Partager

Gmail Facebook X LinkedIn More