Sequential decisions in allocation problems

[eng] In the context of cooperative TU-games, and given an order of players, we consider the problem of distributing the worth of the grand coalition as a sequentia decision problem. In each step of process, upper and lower bounds for the payoff of the players are required related to successive reduced games. Sequentially compatible payoffs are defined as those allocation vectors that meet these recursive bounds. The core of the game is reinterpreted as a set of sequentally compatible payoffs when the Davis-Maschler reduced game is considered (Th.1). Independently of the reduction, the core turns out to be the intersections of the family of the sets of sequentially compatible payoffs corresponding to the different possible orderings (Th.2), so it is in some sense order-independent. Finally, we analyze advantagenous properties for the first player

Sequential decisions in allocation problems

[eng] In the context of cooperative TU-games, and given an order of players, we consider the problem of distributing the worth of the grand coalition as a sequentia decision problem. In each step of process, upper and lower bounds for the payoff of the players are required related to successive reduced games. Sequentially compatible payoffs are defined as those allocation vectors that meet these recursive bounds. The core of the game is reinterpreted as a set of sequentally compatible payoffs when the Davis-Maschler reduced game is considered (Th.1). Independently of the reduction, the core turns out to be the intersections of the family of the sets of sequentially compatible payoffs corresponding to the different possible orderings (Th.2), so it is in some sense order-independent. Finally, we analyze advantagenous properties for the first player

Criteria for hitting probabilities with applications to systems of stochastic wave equations

We develop several results on hitting probabilities of random fields which highlight the role of the dimension of the parameter space. This yields upper and lower bounds in terms of Hausdorff measure and Bessel-Riesz capacity, respectively. We apply these results to a system of stochastic wave equations in spatial dimension k >- 1 driven by a d-dimensional spatially homogeneous additive Gaussian noise that is white in time and colored in space.

mGPT: a probabilistic planner based on heuristic search

We describe the version of the GPT planner to be used in the planning competition. This version, called mGPT, solves mdps specified in the ppddllanguage by extracting and using different classes of lower bounds, along with various heuristic-search algorithms. The lower bounds are extracted from deterministic relaxations of the mdp where alternativeprobabilistic effects of an action are mapped into different, independent, deterministic actions. The heuristic-search algorithms, on the other hand, use these lower bounds for focusing the updates and delivering a consistent value function over all states reachable from the initial state with the greedy policy.

Average performance analysis of circular and hyperbolic geolocation

A comparative performance analysis of four geolocation methods in terms of their theoretical root mean square positioning errors is provided. Comparison is established in two different ways: strict and average. In the strict type, methods are examined for a particular geometric configuration of base stations(BSs) with respect to mobile position, which determines a givennoise profile affecting the respective time-of-arrival (TOA) or timedifference-of-arrival (TDOA) estimates. In the average type, methodsare evaluated in terms of the expected covariance matrix ofthe position error over an ensemble of random geometries, so thatcomparison is geometry independent. Exact semianalytical equationsand associated lower bounds (depending solely on the noiseprofile) are obtained for the average covariance matrix of the positionerror in terms of the so-called information matrix specific toeach geolocation method. Statistical channel models inferred fromfield trials are used to define realistic prior probabilities for therandom geometries. A final evaluation provides extensive resultsrelating the expected position error to channel model parametersand the number of base stations.

Identifying quantitative operation principles in metabolic pathways: a systematic method for searching feasible enzyme activity patterns leading to cellular adaptive responses

Background: Optimization methods allow designing changes in a system so that specific goals are attained. These techniques are fundamental for metabolic engineering. However, they are not directly applicable for investigating the evolution of metabolic adaptation to environmental changes. Although biological systems have evolved by natural selection and result in well-adapted systems, we can hardly expect that actual metabolic processes are at the theoretical optimum that could result from an optimization analysis. More likely, natural systems are to be found in a feasible region compatible with global physiological requirements. Results: We first present a new method for globally optimizing nonlinear models of metabolic pathways that are based on the Generalized Mass Action (GMA) representation. The optimization task is posed as a nonconvex nonlinear programming (NLP) problem that is solved by an outer- approximation algorithm. This method relies on solving iteratively reduced NLP slave subproblems and mixed-integer linear programming (MILP) master problems that provide valid upper and lower bounds, respectively, on the global solution to the original NLP. The capabilities of this method are illustrated through its application to the anaerobic fermentation pathway in Saccharomyces cerevisiae. We next introduce a method to identify the feasibility parametric regions that allow a system to meet a set of physiological constraints that can be represented in mathematical terms through algebraic equations. This technique is based on applying the outer-approximation based algorithm iteratively over a reduced search space in order to identify regions that contain feasible solutions to the problem and discard others in which no feasible solution exists. As an example, we characterize the feasible enzyme activity changes that are compatible with an appropriate adaptive response of yeast Saccharomyces cerevisiae to heat shock Conclusion: Our results show the utility of the suggested approach for investigating the evolution of adaptive responses to environmental changes. The proposed method can be used in other important applications such as the evaluation of parameter changes that are compatible with health and disease states.

Quasiconformal mappings and inequalities involving special functions

This PhD thesis in Mathematics belongs to the field of Geometric Function Theory. The thesis consists of four original papers. The topic studied deals with quasiconformal mappings and their distortion theory in Euclidean n-dimensional spaces. This theory has its roots in the pioneering papers of F. W. Gehring and J. Väisälä published in the early 1960’s and it has been studied by many mathematicians thereafter. In the first paper we refine the known bounds for the so-called Mori constant and also estimate the distortion in the hyperbolic metric. The second paper deals with radial functions which are simple examples of quasiconformal mappings. These radial functions lead us to the study of the so-called p-angular distance which has been studied recently e.g. by L. Maligranda and S. Dragomir. In the third paper we study a class of functions of a real variable studied by P. Lindqvist in an influential paper. This leads one to study parametrized analogues of classical trigonometric and hyperbolic functions which for the parameter value p = 2 coincide with the classical functions. Gaussian hypergeometric functions have an important role in the study of these special functions. Several new inequalities and identities involving p-analogues of these functions are also given. In the fourth paper we study the generalized complete elliptic integrals, modular functions and some related functions. We find the upper and lower bounds of these functions, and those bounds are given in a simple form. This theory has a long history which goes back two centuries and includes names such as A. M. Legendre, C. Jacobi, C. F. Gauss. Modular functions also occur in the study of quasiconformal mappings. Conformal invariants, such as the modulus of a curve family, are often applied in quasiconformal mapping theory. The invariants can be sometimes expressed in terms of special conformal mappings. This fact explains why special functions often occur in this theory.

Optimization of p-cycle protection schemes in optical networks

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème.

Strings of congruent primes in short intervals

Soit $p_1 = 2, p_2 = 3, p_3 = 5,\ldots$ la suite des nombres premiers, et soient $q \ge 3$ et $a$ des entiers premiers entre eux. R\'ecemment, Daniel Shiu a d\'emontr\'e une ancienne conjecture de Sarvadaman Chowla. Ce dernier a conjectur\'e qu'il existe une infinit\'e de couples $p_n,p_{n+1}$ de premiers cons\'ecutifs tels que $p_n \equiv p_{n+1} \equiv a \bmod q$. Fixons $\epsilon > 0$. Une r\'ecente perc\'ee majeure, de Daniel Goldston, J\`anos Pintz et Cem Y{\i}ld{\i}r{\i}m, a \'et\'e de d\'emontrer qu'il existe une suite de nombres r\'eels $x$ tendant vers l'infini, tels que l'intervalle $(x,x+\epsilon\log x]$ contienne au moins deux nombres premiers $\equiv a \bmod q$. \'Etant donn\'e un couple de nombres premiers $\equiv a \bmod q$ dans un tel intervalle, il pourrait exister un nombre premier compris entre les deux qui n'est pas $\equiv a \bmod q$. On peut d\'eduire que soit il existe une suite de r\'eels $x$ tendant vers l'infini, telle que $(x,x+\epsilon\log x]$ contienne un triplet $p_n,p_{n+1},p_{n+2}$ de nombres premiers cons\'ecutifs, soit il existe une suite de r\'eels $x$, tendant vers l'infini telle que l'intervalle $(x,x+\epsilon\log x]$ contienne un couple $p_n,p_{n+1}$ de nombres premiers tel que $p_n \equiv p_{n+1} \equiv a \bmod q$. On pense que les deux \'enonc\'es sont vrais, toutefois on peut seulement d\'eduire que l'un d'entre eux est vrai, sans savoir lequel. Dans la premi\`ere partie de cette th\`ese, nous d\'emontrons que le deuxi\`eme \'enonc\'e est vrai, ce qui fournit une nouvelle d\'emonstration de la conjecture de Chowla. La preuve combine des id\'ees de Shiu et de Goldston-Pintz-Y{\i}ld{\i}r{\i}m, donc on peut consid\'erer que ce r\'esultat est une application de leurs m\'thodes. Ensuite, nous fournirons des bornes inf\'erieures pour le nombre de couples $p_n,p_{n+1}$ tels que $p_n \equiv p_{n+1} \equiv a \bmod q$, $p_{n+1} - p_n < \epsilon\log p_n$, avec $p_{n+1} \le Y$. Sous l'hypoth\`ese que $\theta$, le \og niveau de distribution \fg{} des nombres premiers, est plus grand que $1/2$, Goldston-Pintz-Y{\i}ld{\i}r{\i}m ont r\'eussi \`a d\'emontrer que $p_{n+1} - p_n \ll_{\theta} 1$ pour une infinit\'e de couples $p_n,p_{n+1}$. Sous la meme hypoth\`ese, nous d\'emontrerons que $p_{n+1} - p_n \ll_{q,\theta} 1$ et $p_n \equiv p_{n+1} \equiv a \bmod q$ pour une infinit\'e de couples $p_n,p_{n+1}$, et nous prouverons \'egalement un r\'esultat quantitatif. Dans la deuxi\`eme partie, nous allons utiliser les techniques de Goldston-Pintz-Y{\i}ld{\i}r{\i}m pour d\'emontrer qu'il existe une infinit\'e de couples de nombres premiers $p,p'$ tels que $(p-1)(p'-1)$ est une carr\'e parfait. Ce resultat est une version approximative d'une ancienne conjecture qui stipule qu'il existe une infinit\'e de nombres premiers $p$ tels que $p-1$ est une carr\'e parfait. En effet, nous d\'emontrerons une borne inf\'erieure sur le nombre d'entiers naturels $n \le Y$ tels que $n = \ell_1\cdots \ell_r$, avec $\ell_1,\ldots,\ell_r$ des premiers distincts, et tels que $(\ell_1-1)\cdots (\ell_r-1)$ est une puissance $r$-i\`eme, avec $r \ge 2$ quelconque. \'Egalement, nous d\'emontrerons une borne inf\'erieure sur le nombre d'entiers naturels $n = \ell_1\cdots \ell_r \le Y$ tels que $(\ell_1+1)\cdots (\ell_r+1)$ est une puissance $r$-i\`eme. Finalement, \'etant donn\'e $A$ un ensemble fini d'entiers non-nuls, nous d\'emontrerons une borne inf\'erieure sur le nombre d'entiers naturels $n \le Y$ tels que $\prod_{p \mid n} (p+a)$ est une puissance $r$-i\`eme, simultan\'ement pour chaque $a \in A$.

Les progressions arithmétiques dans les nombres entiers

Le sujet de cette thèse est l'étude des progressions arithmétiques dans les nombres entiers. Plus précisément, nous nous intéressons à borner inférieurement v(N), la taille du plus grand sous-ensemble des nombres entiers de 1 à N qui ne contient pas de progressions arithmétiques de 3 termes. Nous allons donc construire de grands sous-ensembles de nombres entiers qui ne contiennent pas de telles progressions, ce qui nous donne une borne inférieure sur v(N). Nous allons d'abord étudier les preuves de toutes les bornes inférieures obtenues jusqu'à présent, pour ensuite donner une autre preuve de la meilleure borne. Nous allons considérer les points à coordonnés entières dans un anneau à d dimensions, et compter le nombre de progressions arithmétiques qu'il contient. Pour obtenir des bornes sur ces quantités, nous allons étudier les méthodes pour compter le nombre de points de réseau dans des sphères à plusieurs dimensions, ce qui est le sujet de la dernière section.

Complexité de la communication sur un canal avec délai

Nous introduisons un nouveau modèle de la communication à deux parties dans lequel nous nous intéressons au temps que prennent deux participants à effectuer une tâche à travers un canal avec délai d. Nous établissons quelques bornes supérieures et inférieures et comparons ce nouveau modèle aux modèles de communication classiques et quantiques étudiés dans la littérature. Nous montrons que la complexité de la communication d’une fonction sur un canal avec délai est bornée supérieurement par sa complexité de la communication modulo un facteur multiplicatif d/ lg d. Nous présentons ensuite quelques exemples de fonctions pour lesquelles une stratégie astucieuse se servant du temps mort confère un avantage sur une implémentation naïve d’un protocole de communication optimal en terme de complexité de la communication. Finalement, nous montrons qu’un canal avec délai permet de réaliser un échange de bit cryptographique, mais que, par lui-même, est insuffisant pour réaliser la primitive cryptographique de transfert équivoque.

Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Interactive quantum information theory

La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.

Identification des mesures d’inégalité dans les modèles de sélection

Dans ce mémoire, je considère un modèle de sélection standard avec sélection non aléatoire. D’abord, je discute la validité et la ‘‘sharpness ’’ des bornes sur l’intervalle interquantile de la distribution de la variable aléatoire latente non censurée, dérivées par Blundell et al. (2007). Ensuite, je dérive les bornes ‘‘sharp ’’ sur l’intervalle interquantile lorsque la distribution observée domine stochastiquement au premier ordre celle non observée. Enfin, je discute la ‘‘sharpness’’ des bornes sur la variance de la distribution de la variable latente, dérivées par Stoye (2010). Je montre que les bornes sont valides mais pas nécessairement ‘‘sharp’’. Je propose donc des bornes inférieures ‘‘sharp’’ pour la variance et le coefficient de variation de ladite distribution.

Géométrie nodale et valeurs propres de l’opérateur de Laplace et du p-laplacien

La présente thèse porte sur différentes questions émanant de la géométrie spectrale. Ce domaine des mathématiques fondamentales a pour objet d'établir des liens entre la géométrie et le spectre d'une variété riemannienne. Le spectre d'une variété compacte fermée M munie d'une métrique riemannienne $g$ associée à l'opérateur de Laplace-Beltrami est une suite de nombres non négatifs croissante qui tend vers l’infini. La racine carrée de ces derniers représente une fréquence de vibration de la variété. Cette thèse présente quatre articles touchant divers aspects de la géométrie spectrale. Le premier article, présenté au Chapitre 1 et intitulé « Superlevel sets and nodal extrema of Laplace eigenfunctions », porte sur la géométrie nodale d'opérateurs elliptiques. L’objectif de mes travaux a été de généraliser un résultat de L. Polterovich et de M. Sodin qui établit une borne sur la distribution des extrema nodaux sur une surface riemannienne pour une assez vaste classe de fonctions, incluant, entre autres, les fonctions propres associées à l'opérateur de Laplace-Beltrami. La preuve fournie par ces auteurs n'étant valable que pour les surfaces riemanniennes, je prouve dans ce chapitre une approche indépendante pour les fonctions propres de l’opérateur de Laplace-Beltrami dans le cas des variétés riemanniennes de dimension arbitraire. Les deuxième et troisième articles traitent d'un autre opérateur elliptique, le p-laplacien. Sa particularité réside dans le fait qu'il est non linéaire. Au Chapitre 2, l'article « Principal frequency of the p-laplacian and the inradius of Euclidean domains » se penche sur l'étude de bornes inférieures sur la première valeur propre du problème de Dirichlet du p-laplacien en termes du rayon inscrit d’un domaine euclidien. Plus particulièrement, je prouve que, si p est supérieur à la dimension du domaine, il est possible d'établir une borne inférieure sans aucune hypothèse sur la topologie de ce dernier. L'étude de telles bornes a fait l'objet de nombreux articles par des chercheurs connus, tels que W. K. Haymann, E. Lieb, R. Banuelos et T. Carroll, principalement pour le cas de l'opérateur de Laplace. L'adaptation de ce type de bornes au cas du p-laplacien est abordée dans mon troisième article, « Bounds on the Principal Frequency of the p-Laplacian », présenté au Chapitre 3 de cet ouvrage. Mon quatrième article, « Wolf-Keller theorem for Neumann Eigenvalues », est le fruit d'une collaboration avec Guillaume Roy-Fortin. Le thème central de ce travail gravite autour de l'optimisation de formes dans le contexte du problème aux valeurs limites de Neumann. Le résultat principal de cet article est que les valeurs propres de Neumann ne sont pas toujours maximisées par l'union disjointe de disques arbitraires pour les domaines planaires d'aire fixée. Le tout est présenté au Chapitre 4 de cette thèse.