La théorie de la rigidité étudie l'unicité des réalisations des graphes, i.e., des charpentes. Initialement motivée par l'ingénierie des structures, la théorie de la rigidité trouve aujourd'hui des applications dans plusieurs domaines importants comme la prédiction de la flexibilité des protéines, la conception assistée par ordinateur, la localisation dans les réseaux des capteurs, etc. Cette thèse traite une grande variété de problèmes concernant différents types de rigidité, qui correspondent à différents niveaux d'unicité (locale/infinitésimale, globale et universelle) dans des modèles variés de charpentes. D'abord, nous développons des résultats sur la construction récursive et la décomposition des graphes avec des conditions mixtes de sparsité ainsi que des résultats sur le packing des arborescences avec des contraintes de matroïde. Ces résultats sont alors utilisés pour obtenir des caractérisations de la rigidité infinitésimale des charpentes avec des contraintes mixtes. Nous étudions aussi l'effet des opérations d'extension sur des charpentes et étendons un résultat connu sur la préservation de la rigidité globale d'$1$-extension dans les charpentes à direction et à longueur de la dimension deux aux dimensions supérieures. Pour la rigidité universelle, un sujet que l'on connait très peu, nous obtenons une caractérisation complète pour la classe des charpentes biparties complètes sur la ligne. Nous généralisons aussi une condition suffisante pour la rigidité universelle des charpentes en permettant des positions non générales. / The theory of rigidity studies the uniqueness of realizations of graphs, i.e., frameworks. Originally motivated by structural engineering, rigidity theory nowadays finds applications in many important problems such as predicting protein flexibility, Computer-Aided Design, sensor network localization, etc. The present thesis treats a wide range of problems concerning different kinds of rigidity, corresponding to different scopes of uniqueness (local/infinitesimal, global and universal), in various types of frameworks. First, we develop results in inductive construction and decomposition of graphs with mixed sparsity conditions as well as results on the packing of arborescences with matroidal constraints. These results are then used to obtain characterizations of infinitesimal rigidity in frameworks with mixed constraints. We also investigate the effect of extension operations on frameworks and extend a known result on the global rigidity preservation of $1$-extension on direction-length frameworks in dimension two to all dimensions. For universal rigidity, where little is known, we obtain a complete characterization for the class of complete bipartite frameworks on the line. We also generalize a sufficient condition for the universal rigidity of frameworks by allowing non-general positions.

Étant donnés un graphe simple non orienté G = (V, E) et un sommet particulier r dans V appelé racine, un arbre enraciné, ou r-arbre, de G est soit le graphe nul soit un arbre contenant r. Si un vecteur de capacités sur les sommets est donné, un sous-graphe de G est dit borné si le degré de chaque sommet dans le sous-graphe est inférieur ou égal à sa capacité. Soit w un vecteur de poids sur les arêtes et p un vecteur de profits sur les sommets. Le problème du r-arbre borné maximum (MBrT, de l’anglais Maximum Bounded r-Tree) consiste à trouver un r-arbre borné T = (U, F) de G tel que son poids soit maximisé. Si la contrainte de capacité du problème MBrT est relâchée, nous obtenons le problème du r-arbre maximum (MrT, de l’anglais Maximum r-Tree). Cette thèse contribue à l’étude des problèmes MBrT et MrT.Tout d’abord, ces deux problèmes sont formellement définis et leur complexité est étudiée. Nous présentons ensuite des polytopes associés ainsi qu’une formulation pour chacun d’entre eux. Par la suite, nous proposons plusieurs algorithmes combinatoires pour résoudre le problème MBrT (et donc le problème MrT) en temps polynomial sur les arbres, les cycles et les cactus. En particulier, un algorithme de programmation dynamique est utilisé pour résoudre le problème MBrT sur les arbres. Pour les cycles, nous sommes amenés a considérer trois cas différents pour lesquels le problem MBrT se réduit à certains problèmes polynomiaux. Pour les cactus, nous montrons tout d’abord que le problème MBrT peut être résolu en temps polynomial sur un type de graphes appelé cactus basis. En utilisant une série de décompositions en sous-problèmes sur les arbres et les cactus basis, nous obtenons un algorithme pour les graphes de type cactus.La deuxième partie de ce travail étudie la structure polyédrale de trois polytopes associés aux problèmes MBrT et MrT. Les deux premiers polytopes, Bxy(G,r,c) et Bx(G,r,c) sont associés au problème MBrT. Tous deux considèrent des variables sur les arêtes de G, mais seuls Bxy(G,r,c) possède également des variables sur les sommets de G. Le troisième polytope, Rx(G,r), est associé au problème MrT et repose uniquement sur les variables sur les arêtes. Pour chacun de ces trois polytopes, nous étudions sa dimension, caractérisons certaines inégalités définissant des facettes, et présentons les moyens possibles de décomposition. Nous introduisons également de nouvelles familles de contraintes. L’ajout de ces contraintes nous permettent de caractériser ces trois polytopes dans plusieurs classes de graphes.Pour finir, nous étudions les problèmes de séparation pour toutes les inégalités que nous avons trouvées jusqu’ici. Des algorithmes polynomiaux de séparation sont présentés, et lorsqu’un problème de séparation est NP-difficile, nous donnons des heuristiques de séparation. Tous les résultats théoriques développés dans ce travail sont implémentés dans plusieurs algorithmes de coupes et branchements auxquels une matheuristique est également jointe pour générer rapidement des solutions réalisables. Des expérimentations intensives ont été menées via le logiciel CPLEX afin de comparer les formulations renforcées et originales. Les résultats obtenus montrent de manière convaincante la force des formulations renforcées. / Given a simple undirected graph G = (V, E) with a so-called root node r in V, a rooted tree, or an r-tree, of G is either the empty graph, or a tree containing r. If a node-capacity vector c is given, then a subgraph of G is said to be bounded if the degree of each node in the subgraph does not exceed its capacity. Let w be an edge-weight vector and p a node-price vector. The Maximum Bounded r-Tree (MBrT) problem consists of finding a bounded r-tree T = (U, F) of G such that its weight is maximized. If the capacity constraint from the MBrT problem is relaxed, we then obtain the Maximum r-Tree (MrT) problem. This dissertation contributes to the study of the MBrT problem and the MrT problem.First we introduce the problems with their definitions and complexities. We define the associated polytopes along with a formulation for each of them. We present several polynomial-time combinatorial algorithms for both the MBrT problem (and thus the MrT problem) on trees, cycles and cactus graphs. Particularly, a dynamic-programming-based algorithm is used to solve the MBrT problem on trees, whereas on cycles we reduce it to some polynomially solvable problems in three different cases. For cactus graphs, we first show that the MBrT problem can be solved in polynomial time on a so-called cactus basis, then break down the problem on any cactus graph into a series of subproblems on trees and on cactus basis.The second part of this work investigates the polyhedral structure of three polytopes associated with the MBrT problem and the MrT problem, namely Bxy(G, r, c), Bx(G, r, c) and Rx(G, r). Bxy(G, r, c) and Bx(G, r, c) are polytopes associated with the MBrT problem, where Bxy(G, r, c) considers both edge- and node-indexed variables and Bx(G, r, c) considers only edge-indexed variables. Rx(G, r) is the polytope associated with the MrT problem that only considers edge-indexed variables. For each of the three polytopes, we study their dimensions, facets as well as possible ways of decomposition. We introduce some newly discovered constraints for each polytope, and show that these new constraints allow us to characterize them on several graph classes. Specifically, we provide characterization for Bxy (G, r, c) on cactus graphs with the help of a decomposition through 1-sum. On the other hand, a TDI-system that characterizes Bx(G,r,c) is given in each case of trees and cycles. The characterization of Rx(G,r) on trees and cycles then follows as an immediate result.Finally, we discuss the separation problems for all the inequalities we have found so far, and present algorithms or cut-generation heuristics accordingly. A couple of branch-and-cut frameworks are implemented to solve the MBrT problem together with a greedy-based matheuristic. We compare the performances of the enhanced formulations with the original formulations through intensive computational test, where the results demonstrate convincingly the strength of the enhanced formulations.

La construction de modèles qui protègent contre les incertitudes dans les données, telles que la variabilité de l'information et l'imprécision est une des principales préoccupations en optimisation sous incertitude. L'incertitude peut affecter différentes domaines, comme le transport, les télécommunications, la finance, etc. ainsi que les différentes parts d'un problème d'optimisation, comme les coefficients de la fonction objectif et /ou les contraintes. De plus, l'ensemble des données incertaines peut être modélisé de différentes façons, comme sous ensembles compactes et convexes de l´espace réel de dimension n, polytopes, produits Cartésiens des intervalles, ellipsoïdes, etc.<p><p>Une des approches possibles pour résoudre des tels problèmes est de considérer les versions minimax regret, pour lesquelles résoudre un problème sous incertitude revient à trouver une solution qui s'écarte le moins possible de la valeur solution optimale dans tout les cas. <p><p>Dans le cas des incertitudes définies par intervalles, les versions minimax regret de nombreux problèmes combinatoires polynomiaux sont NP-difficiles, d'ou l'importance d'essayer de réduire l'espace des solutions. Dans ce contexte, savoir quand un élément du problème, représenté par une variable, fait toujours ou jamais partie d'une solution optimal pour toute réalisation des données (variables 1-persistentes et 0-persistentes respectivement), constitue une manière de réduire la taille du problème. Un des principaux objectifs de cette thèse est d'étudier ces questions pour quelques problèmes d'optimisation combinatoire sous incertitude.<p><p>Nous étudions les versions minimax regret du problème du choix de p éléments parmi m, de l'arbre couvrant minimum et des deux problèmes de plus court chemin. Pour de tels problèmes, dans le cas des incertitudes définis par intervalles, nous étudions le problème de trouver les variables 1- et 0-persistentes. Nous présentons une procédure de pre-traitement du problème, lequel réduit grandement la taille des formulations des versions de minimax regret.<p><p>Nous nous intéressons aussi à la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont incertains et l'ensemble des données incertaines est polyédral. Dans le cas où l'ensemble des incertitudes est défini par des intervalles, le problème de trouver le regret maximum est NP-difficile. Nous présentons des cas spéciaux ou les problèmes de maximum regret et de minimax regret sont polynomiaux. Dans le cas où l´ensemble des incertitudes est défini par un polytope, nous présentons un algorithme pour trouver une solution exacte au problème de minimax regret et nous discutons les résultats numériques obtenus dans un grand nombre d´instances générées aléatoirement.<p><p>Nous étudions les relations entre le problème de 1-centre continu et la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont évalués à l´aide des intervalles. En particulier, nous décrivons la géométrie de ce dernier problème, nous généralisons quelques résultats en théorie de localisation et nous donnons des conditions sous lesquelles certaines variables peuvet être éliminées du problème. Finalement, nous testons ces conditions dans un nombre d´instances générées aléatoirement et nous donnons les conclusions. / Doctorat en sciences, Orientation recherche opérationnelle / info:eu-repo/semantics/nonPublished

Cette thèse apporte une généralisation du principe de recommandation des systèmes de recommandation. Au lieu de considérer une recommandation comme un item, elle est considérée comme une combinaison constituée de plusieurs items suivant un pattern donné. Une recommandation d'un seul item est alors un cas particulier de ce type de recommandation. L’architecture de système de recommandation proposé se base sur une architecture dérivée des travaux en systèmes hypermédia adaptatifs. Trois couches sont définies : une couche sémantique, une couche utilisateur et une couche intelligence. La couche sémantique est constituée de deux sous-couches, une sous-couche modélisant le contenu suivant la connaissance générale du domaine et une sous-couche modélisant le contenu suivant la connaissance spécifique à l'application, plus précisément spécifique aux possibles contraintes des utilisateurs dans l'application. Cette deuxième partie permet de prendre en compte le savoir-faire du fournisseur de l’offre dans les propositions du système de recommandation. La couche utilisateur modélise l’utilisateur au sein du système de recommandation et la couche intelligence contient le processus de recommandation. Nous proposons de décomposer ce dernier en deux sous-processus principaux, un processus dit de projection des individus du domaine sur les profils utilisateurs et un processus de recherche combinatoire. Le premier apporte une pondération, appelée note dans la plupart des systèmes de recommandation, donnant les intérêts probables des utilisateurs pour les différents items. Le processus de recherche combinatoire recherche parmi la multitude de combinaisons possibles, une solution convenable (optimale si possible) à proposer à l'utilisateur. Cette architecture de système de recommandation combinatoire est appliquée au domaine touristique pour l'entreprise Côte-d'Or Tourisme impliquée dans le contrat de recherche. Le but de cette application est de proposer à l'utilisateur un ensemble d'offres touristiques sous forme de séjour. Ce problème touristique amène à la définition formelle d'un problème d'optimisation combinatoire qui est une variante d'un sous-problème du problème de sac à dos. Pour résoudre ce genre de problème, il est nécessaire d'utiliser une métaheuristique afin de tendre vers une bonne solution en un temps raisonnable. Nous présentons un algorithme basé sur le recuit simulé et un algorithme multi-objectif pour la résolution de ce problème. L’instanciation de chaque couche de l’architecture pour le système touristique est décrite en détail. Enfin, cette thèse présente une application mobile faisant office d’interface utilisateur avec le système de recommandation touristique et elle présente les développements techniques nécessaires à ce projet, étant donné son contexte industriel. / This thesis gives a generalization of the recommendation principle of recommender systems. Instead of considering a recommendation as an item, it is considered as a combination of several items following a given pattern. A recommendation of a unique item is then a particular case of this type of recommendation. The proposed recommender system framework is based on an architecture derived from work in adaptive hypermedia systems. Three layers are defined: a semantic layer, a user layer and an intelligence layer. The semantic layer consists of two sub-layers, a sub-layer modeling the content according to the general knowledge of the domain and a sub-layer modeling the content according to the specific knowledge of the application. This second sub-layer allows taking into account the expertise of the offer’s supplier for the proposals of the recommender system. The user layer models the user into the recommender system and the intelligence layer contains recommendation process. We propose to decompose the adaptation into two main processes, a process called projection of domain’s individuals on user profiles and a combinatorial research process. The first brings a weight, called the note in most recommender systems, giving probable users’ interests on the different items. The combinatorial research process searches among the many possible combinations a suitable solution (optimal if possible) to propose to the user. This framework of combinatory recommender systems is applied to the domain of tourism for the company Côte-d'Or Tourisme implied in the research contract. The purpose of this application is to offer the user a set of tourism offers in the form of journey. This tourism problem leads to the formal definition of a combinatory optimization problem which is a variant of the knapsack problem. To resolve this kind of problem, it is necessary to use a metaheuristic to tend toward a good solution in a reasonable time. We present an algorithm based on simulated annealing and a multi-objective algorithm to solve this problem. The instantiation of each layer of the framework for the tourism system is described in detail. Finally, this thesis presents a mobile application serving as a user with the tourism recommender system and it presents the technical developments for this project.

Le secteur des semi-conducteurs a connu un développement considérable ces dernières décennies, du fait des nouvelles applications de la microélectronique dans l'industrie. Le processus de fabrication est réputé pour sa complexité. L'un des ateliers les plus critiques de la production, l'atelier de photolithographie, est régi par un ensemble conséquent de contraintes de production. La multiplicité des ressources utilisées, le nombre important de produits traités, en font une zone importante à optimiser. Les objectifs de la thèse ont été de modéliser cet atelier sous la forme d'un problème d'ordonnancement sur machines parallèles et d'optimiser plusieurs critères jugés pertinents pour évaluer la qualité des solutions. Des résultats en termes de complexité, et d'algorithmes de résolution, ont permis une application industrielle, dans la mesure où un logiciel d'optimisation destiné à l'ordonnancement des lots en photolithographie a été développé. / Semiconductor manufacturing has grown considerably in recent decades, due to new industrial applications of microelectronic devices. The related manufacturing process is known to be complex. A bottleneck process step, the photolithography workshop, gathers various types of constraints, related to the number of auxiliary resources and the tools characteristics. The aims of the thesis were to model this workstation as a parallel machine scheduling problem and to optimize various criteria, determined by industrial needs. Some complexity results are provided and optimization algorithms led to an industrial application, i.e. a software providing optimized schedules in a specific fab.

Un des principaux défis de la bioinformatique moderne est de saisir le sens des données biologiques en constante croissance. Il est prépondérant de trouver de bons modèles pour toutes ces données, modèles qui servent à la fois à expliquer les données et à produire des réponses aux questions biologiques sous-jacentes. Une des nombreuses difficultés d’une telle approche est la grande variété dans les types des données manipulées. La biologie computationnelle moderne propose des approches qui combinent ces types de données dans des techniques dites intégratives. Cette thèse contribue au problème de l’identification de module biologique en intégrant les informations de conservation dans les modèles modernes d’identification d’ensemble de protéines. Nous introduisons un modèle pour la détection de modules connexes actifs et conservés, c’est-à-dire des modules connexes dont une majorité d’éléments sont similaires entre deux espèces. Nous présentons une formulation de notre modèle sous forme de programmation linéaire en nombres entiers, et proposons un algorithme branch-and-cut qui résout le modèle à l’optimalité en temps raisonnable. Nous appliquons notre modèle sur des données de différentiation cellulaire, à savoir les cellules Th0 en Th17 pour l’humain et la sourie. Nous analysons également notre modèle du point du vue de la complexité algorithmique, et fournissons des résultats pour le cas général ainsi que des cas spéciaux. / One of the major challenge for modern bioinformatics is making sense of the ever increasing size of biological data. Finding good models for all this data, models that can both explain the data and provide insight into biological questions, is paramount. One of the many difficulties of such path is the variety in the types of data. Modern computational biology approaches combine these many data into integrative approaches, that combine the knowledge inside the data in the hope to extract higher level information. This thesis contribute to the biological module identification problem by integrating conservation information with modern models of modular detection of protein sets. We introduce a model for the detection of conserved active connected modules, that is connected modules that are conversed across two species. These active connected modules are similar in sequence composition between the two species. We present a mixed-integer linear programming formulation of our model, and propose a branch-and-cut algorithm to solve to provable optimality in reasonable run time. We apply our model to cell line differentiation data, namely Th0 into Th17 for both human and mouse. We also analyse the model from a complexity standpoint, and provide general as well as special cases complexity results.

Les problèmes de partitionnement de graphique sont une classe bien connue des problèmes d'optimisation combinatoire NP-difficiles avec un large éventail d'applications, telles que la conception de plans VLSI, la physique statistique, la planification d'une équipe sportive, la segmentation d'images et la structuration de protéines. En raison de la grande complexité de ces problèmes, les approches heuristiques et métaheuristiques sont couramment utilisées pour aborder les problèmes difficiles. Cette thèse considère trois problèmes représentatifs de cette famille, incluant le problème "max-k-cut", le problème "max-bisection" et le problème de séparation de sommets (VSP). Elle vise à élaborer des algorithmes heuristiques efficaces basés sur une ensemble d'opérateurs de recherche complémentaires. Plus précisément, nous développons une heuristique à opérateur multiple (MOH) pour "max-k-cut", un algorithme de recherche Tabu itérée (ITS) pour "max-bisection" et un algorithme "path relinking" (PR-VSP) pour VSP. Des résultats expérimentaux sur des jeux de test standard démontrent que les algorithmes proposés rivalisent favorablement avec les approches existantes de la littérature. L'utilisation combinée de plusieurs opérateurs de recherche est analysée afin de mettre en évidence l'influence de ces opérateurs sur la performance des algorithmes. / Graph partitioning problems are a class of well-known NP-hard combinatorial optimization problems with a wide range of applications, such as VLSI layout design, statistical physics, sports team scheduling, image segmentation, and protein conformation for instances. This thesis considers three representative problems in this family, including the max-k-cut problem, the max-bisection problem and the vertex separator problem (VSP). Due to high computational complexity, heuristic and metaheuristic approaches are commonly used for approximating the challenging problems. This thesis is devoted to developing efficient metaheuristic algorithms based on a collection of complementary search operators. Specifically, we develop a multiple operator heuristic (MOH) for max-k-cut, an iterated tabu search (ITS) algorithm for max-bisection and a path relinking (PR-VSP) algorithm for VSP. Extensive computational experiments and comparisons demonstrate that the proposed algorithms compete favorably with state-of-the-art approaches in the literature. The combined use of multiple search operators is analyzed to shed lights on the influence over the performance of the algorithms.

Le concept de réserve voie a été présenté comme une stratégie de gestion du trafic et a de nombreuses applications dans la vie réelle. Des études antérieures dans la littérature se concentrent principalement sur l'impact de la réservation de la voie dans une région locale du réseau de transport. Dans cette thèse, les problèmes de réservation de voies sont étudiés dans le but de minimiser l'impact sur le trafic total par la réservation optimale des voies dans un réseau de transport. Nous avons d’abord se concentrer sur le problème de réservation de voie (LRP) pour le transport automatisé pour les poids lourds avec temps de déplacement statique. Ce travail est généralisé au problème de réservation voies avec une capacité limitée de la voie (CLRP) pour les grands événements spéciaux. Enfin, le problème de réservation de voies avec le temps de déplacement dépendant du temps (LRP-TT), et le problème de réservation voies avec la vitesse de déplacement dépendant du temps (LRP-TS) sont étudiés. Pour chacun des problèmes étudiés, les modèles mathématiques appropriés sont formulés, leurs complexités sont démontrées. Différentes méthodes de résolution sont explorées, y compris exacte cut-and-solve méthode, cut-and-solve et méthod de coupe combinée, et la méthode de recherche tabou. Les performances des algorithmes proposés sont évaluées par des instances générées au hasard. Les résultats numériques ont montré que les algorithmes proposés sont plus efficaces pour résoudre les problèmes étudiés que le logiciel commercial référence CPLEX / The concept of lane reservation has been introduced as a traffic management strategy and has many applications in real life. Previous studies in the literature mainly focus on the impact of lane reservation in a local region of transportation network. In this thesis optimal lane reservation problems are studied with the objective to minimize impact on total traffic by optimally setting reserved lanes in a transportation network. We firstly focus on the lane reservation problem (LRP) for automated truck freight transportation with static link travel time. This primary work has been extended to the capacitated lane reservation problem (CLRP) for large-scale special events. Finally, lane reservation problem with time-dependent travel time (TTLRP), and lane reservation problem with time-dependent travel speed (TSLRP) are studied. For each of the considered problems, appropriate mathematical models are formulated, their complexities are demonstrated. Different resolution methods are explored including exact cut-and-solve method, cut-and-solve and cutting plane combined method, and Tabu-search method. The performance of the proposed algorithms is evaluated by randomly generated instances. Numerical results have shown that the proposed algorithms are more effective to solve the considered problems than the reference commercial package CPLEX

Au cours de cette thèse, nous avons abordé des problématiques liées à l’optimisation de déploiement et la localisation de cible dans les réseaux de capteurs. Nous avons tout d'abord proposé un premier modèle pour l’optimisation de deux objectifs contradictoires : le nombre de capteurs déployés ainsi que la précision de la localisation. Quatre algorithmes multi-objectifs classiques ont été implémentés, et des versions hybrides ont également été proposées.Une variante du précédent problème est également étudiée, dédiée aux applications de localisation indoor. Les algorithmes proposés pour le premier problème n'ont montré qu'une efficacité relative au cours des premières expérimentations. Une nouvelle heuristique est alors développée, et les résultats ont montré de très bonnes performances sur les instances de taille réduite, ainsi que de bien meilleures performances que les autres algorithmes implémentés sur des instances de grande taille.Enfin, la notion de connectivité et de couverture est également traitée et intégrée dans un modèle linéaire de déploiement. Un algorithme Branch and Bound a été développé afin de traiter ce problème, puis des tests ont été effectués afin de le comparer aux solveurs linéaires actuels / In this thesis, a joint approach for deployment optimization and target tracking in sensor networks is developed. First, we have proposed a linear model to minimize the number of deployed sensors and maximize the accuracy of the localization. We have also implemented several multi-objective methods and proposed hybridization for some of them.We have also proposed a modification of the previous model, taking into account the indoor localization constraints. Two methods of the previous problem have been used, and a specific heuristic has been developed.Finally, two linear models taking into account coverage and connectivity have been proposed. A Branch and Bound algorithm has also been developed, considering a geometric lower bound and two properties to reduce the number of fathomed nodes

Dans un graphe orienté contenant un nœud appelé racine, un sous ensemble de nœuds appelés terminaux et une pondération sur les arcs, le problème de l’arborescence de Steiner (DST) consiste en la recherche d’une arborescence de poids minimum contenant pour chaque terminal un chemin de la racine vers ce terminal. Ce problème est NP-Complet. Cette thèse se penche sur l’étude de l’approximabilité de ce problème. Sauf si P=NP, il n’existe pas pour ce problème d’approximation de rapport constant ou logarithmique en k, oú k est le nombre de terminaux. Le plus petit rapport d’approximation connu est O (k") où " est un réel strictement positif. Dans la première partie, nous donnons trois algorithmes d’approximation : un algorithme glouton efficace qui associe deux techniques d’approximations connues pour DST, un algorithme dans le cas des graphes structurés en paliers qui étudie l’approximabilité du problème quand les terminaux sont éloignés de la racine, et un algorithme exponentiel qui combine un algorithme d’approximation et un algorithme exact, dont le rapport d’approximation et la complexité temporelle sont paramétrés par le nombre de terminaux couverts par l’algorithme exact. Dans la seconde partie, nous étudions deux problèmes issus de DST auquel est ajoutée une contrainte sur les nœuds de branchement. Cette contrainte réduit le nombre de solutions réalisables et peut faciliter la recherche d’une solution optimale parmi ce sous-ensemble de solutions. En fonction de la contrainte, nous étudions la possibilité de la trouver en temps polynomial et quel est le rapport d’approximation entre cette solution et la solution du problème non contraint / The directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ)$ where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem