La première partie de cette thèse s'intéresse au groupage de trafic dans les réseaux de télécommunications. La notion de groupage de trafic correspond à l'agrégation de flux de faible débit dans des conduits de plus gros débit. Cependant, à chaque insertion ou extraction de trafic sur une longueur d'onde il faut placer dans le noeud du réseau un multiplexeur à insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilisée dans le noeud, ce qui représente un coût d'équipements important. Les objectifs du groupage de trafic sont d'une part le partage efficace de la bande passante et d'autre part la réduction du coût des équipements de routage. Nous présentons des résultats d'inapproximabilité, des algorithmes d'approximation, un nouveau modèle qui permet au réseau de pouvoir router n'importe quel graphe de requêtes de degré borné, ainsi que des solutions optimales pour deux scénarios avec trafic all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de manière dynamique. La deuxième partie de la thèse s'intéresse aux problèmes consistant à trouver des sous-graphes avec contraintes sur le degré. Cette classe de problèmes est plus générale que le groupage de trafic, qui est un cas particulier. Il s'agit de trouver des sous-graphes d'un graphe donné avec contraintes sur le degré, tout en optimisant un paramètre du graphe (très souvent, le nombre de sommets ou d'arêtes). Nous présentons des algorithmes d'approximation, des résultats d'inapproximabilité, des études sur la complexité paramétrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une méthodologie générale qui permet de résoudre efficacement cette classe de problèmes (et de manière plus générale, la classe de problèmes tels qu'une solution peut être codé avec une partition d'un sous-ensemble des sommets) pour les graphes plongés dans une surface. Finalement, plusieurs annexes présentent des résultats sur des problèmes connexes.

Nous nous intéressons dans cette thèse à différents types de réseaux (optiques, sans-fil, pair-à-pair) ayant chacun leurs spécificités mais partageant des problématiques communes : assurer la meilleure qualité de services possible, garantir la stabilité du système, minimiser les ressources et donc le coût de fonctionnement. Tout d'abord, nous étudions le problème de la reconfiguration du routage dans les réseaux optiques consistant à rerouter les requêtes de connexion en minimisant les perturbations pour les utilisateurs. Puis, nous nous intéressons au problème de la détermination de routages efficaces en énergie dans les réseaux coeur. Pour ce faire, nous étudions le problème de trouver des routages minimisant le nombre d'équipements utilisés. Ensuite, nous nous intéressons aux algorithmes d'ordonnancement des liens dans les réseaux sans-fil en présence d'interférence. Enfin, nous considérons le problème de stockage de données dans les réseaux pair-à-pair. Nous étudions l'impact de différentes politiques de placement sur la durée de vie des données et nous déterminons un choix de placement optimal. Pour résoudre ces problèmes, nous utilisons les outils théoriques des mathématiques discrètes (graphes, configurations, optimisation combinatoire), d'algorithmique (complexité, algorithmique distribuée) et de probabilités.

Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.

In this thesis, we will discuss the construction of algorithms for solving Constraint Satisfaction Problems (CSPs), and describe two new ways of approaching them. Both approaches are based on the idea that it is sometimes faster to solve a large number of restricted problems than a single, large, problem. One of the strong points of these methods is that the intuition behind them is fairly simple, which is a definite advantage over many techniques currently in use. The first method, the covering method, can be described as follows: We want to solve a CSP with n variables, each having a domain with d elements. We have access to an algorithm which solves problems where the domain has size e < d, and we want to cover the original problem using a number of restricted instances, in such a way that the solution set is preserved. There are two ways of doing this, depending on the amount of work we are willing to invest; either we construct an explicit covering and end up with a deterministic algorithm for the problem, or we use a probabilistic reasoning and end up with a probabilistic algorithm. The second method, called the partitioning method, relaxes the demand on the underlying algorithm. Instead of having a single algorithm for solving problems with domain less than d, we allow an arbitrary number of them, each solving the problem for a different domain size. Thus by splitting, or partitioning, the domain of the large problem, we again solve a large number of smaller problems before arriving at a solution. Armed with these new techniques, we study a number of different problems; the decision problems (d, l)-CSP and k-Colourability, together with their counting counterparts, as well as the optimisation problems Max Ind CSP, Max Value CSP, Max CSP, and Max Hamming CSP. Among the results, we find a very fast, polynomial space algorithm for determining k-colourability of graphs.

We propose a situation in which a single employee is responsible for processing incoming claims to an insurance company that can be classified as being one of two possible types. More specifically, we consider a priority-based system having separate buffers to store high priority and low priority incoming claims. We construct a mathematical model and perform queueing analysis to evaluate the performance of this priority-based system, which incorporates the possibility of claims being redistributed, lost, or prematurely processed.

We propose a situation in which a single employee is responsible for processing incoming claims to an insurance company that can be classified as being one of two possible types. More specifically, we consider a priority-based system having separate buffers to store high priority and low priority incoming claims. We construct a mathematical model and perform queueing analysis to evaluate the performance of this priority-based system, which incorporates the possibility of claims being redistributed, lost, or prematurely processed.

To overcome the curse of dimensionality, dimension reduction is important and necessary for understanding the underlying phenomena in a variety of fields. Dimension reduction is the transformation of high-dimensional data into a meaningful representation in the low-dimensional space. It can be further classified into feature selection and feature extraction. In this thesis, which is composed of four projects, the first two focus on feature selection, and the last two concentrate on feature extraction. The content of the thesis is as follows. The first project presents several efficient methods for the sparse representation of a multiple measurement vector (MMV); some theoretical properties of the algorithms are also discussed. The second project introduces the NP-hardness problem for penalized likelihood estimators, including penalized least squares estimators, penalized least absolute deviation regression and penalized support vector machines. The third project focuses on the application of manifold learning in the analysis and prediction of 24-hour electricity price curves. The last project proposes a new hessian regularized nonlinear time-series model for prediction in time series.

In this thesis, we consider multiobjective combinatorial optimization problems. We address two main topics. We first address the polynomially solvable cases of the Traveling Salesperson Problem and the Bottleneck Traveling Salesperson Problem. We consider multiobjective versions of these problems with different combinations of objective functions, analyze their computational complexities and develop exact algorithms where possible. We next consider generating extreme supported nondominated points of multiobjective integer programming problems for any number of objective functions. We develop two algorithms for this purpose. The first one is an exact algorithm and finds all such points. The second algorithm finds only a subset of extreme supported nondominated points providing a worst case approximation for the remaining points.

Deux défis de la théorie du codage algébrique sont traités dans cette thèse. Le premier est le décodage efficace (dur et souple) de codes de Reed--Solomon généralisés sur les corps finis en métrique de Hamming. La motivation pour résoudre ce problème vieux de plus de 50 ans a été renouvelée par la découverte par Guruswami et Sudan à la fin du 20ème siècle d'un algorithme polynomial de décodage jusqu'au rayon Johnson basé sur l'interpolation. Les premières méthodes de décodage algébrique des codes de Reed--Solomon généralisés faisaient appel à une équation clé, c'est à dire, une description polynomiale du problème de décodage. La reformulation de l'approche à base d'interpolation en termes d'équations clés est un thème central de cette thèse. Cette contribution couvre plusieurs aspects des équations clés pour le décodage dur ainsi que pour la variante décodage souple de l'algorithme de Guruswami--Sudan pour les codes de Reed--Solomon généralisés. Pour toutes ces variantes un algorithme de décodage efficace est proposé. Le deuxième sujet de cette thèse est la formulation et le décodage jusqu'à certaines bornes inférieures sur leur distance minimale de codes en blocs linéaires cycliques. La caractéristique principale est l'intégration d'un code cyclique donné dans un code cyclique produit (généralisé). Nous donnons donc une description détaillée du code produit cyclique et des codes cycliques produits généralisés. Nous prouvons plusieurs bornes inférieures sur la distance minimale de codes cycliques linéaires qui permettent d'améliorer ou de généraliser des bornes connues. De plus, nous donnons des algorithmes de décodage d'erreurs/d'effacements [jusqu'à ces bornes] en temps quadratique.

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé. / The automata non emptiness intersection problem is to determine whether several deterministic finite automata accept a word in common. It is known to be PSPACE-complete (resp. NL-complete) whenever the number of automata is not bounded (resp. bounded by a constant). In this work, we study the complexity of the automata intersection problem for several types of languages and automata such as unary languages, (abelian) group automata, commutative languages and finite languages. We raise the issue of limiting the number of final states to at most two in the automata involved. This way, we obtain relationships with some algebraic problems and an interesting classification of automata intersection problems inside the class P. Finally, we briefly consider the bounded version of the automata intersection problem.