Search

The greedy approach is natural for the design of algorithms. It is fast, easy to implement, has a good performance on average, and is applicable to many optimization problems in various settings. For those reasons, it is an important heuristic in practice. In this thesis, we present greedy algorithms for three different NP-hard optimization problems. We discuss the relation between those algorithms, their proof techniques and the structure of the problems under study. In the first part of this thesis, we focus on the Maximum Coverage problem with a connectivity constraint, which comes up for the design of wireless networks. We show that the problem is NP-hard, even when the coverage and the connectivity are induced by a set of unit disks in the plane. For that special case, we show that greedily picking two disks so as to maximize the marginal area covered while correctness achieves a 2-approximation. We further improve the approximation ratio by providing a PTAS for this problem with a small resource augmentation, using Arora’s shifted grid dissection technique. In the second part of this thesis, we focus on the Maximum Independent Set problem. A natural approach is to repeatedly pick a vertex of minimum degree, and remove it and its neighbours from the graph. We present a new technique to analyze the performance of this greedy approach in various classes of graphs and address the following question: if there are several minimun-degree vertices, what vertex should the greedy algorithm pick in order to maximise the size of the final solution ? With this tool, we design an ”ultimate tie-breaking” rule that leads to the best possible approximation ratio for sub-cubic graphs and for this type of greedy algorithms. We complement this by lower bound results that show that designing good tie-breaking rules is a difficult task. The third and last part of the thesis is devoted to the Maximum Integral Multiflows problem. The problem is difficult and well-studied. For instance, a constant factor approximation is unlikely to exist even when the supply graph is planar and cubic. In the special case where the supply graph together with the demand edges form a bounded genus graph, we present a constant factor approximation algorithm. The algorithm consists of a succession of greedy procedures that exploit topological properties of graphs and curves on surfaces., L’approche gloutonne est naturelle pour concevoir un algorithme. Elle permet la conception d’algorithmes rapides, faciles à implémenter, qui produisent en moyenne des solutions de qualité, pour de nombreux problèmes d’optimisation. Pour ces raisons, c’est une heuristique importante en pratique. Dans cette thèse, nous présentons des algorithmes gloutons pour trois problèmes d’optimisation NP-difficiles. Nous discutons les relations entre ces algorithmes, leurs techniques de preuve et la structure des problèmes étudiés. Dans la première partie de cette thèse, on se concentre sur le problème de la couverture maximale avec une contrainte de connexité, contrainte que l’on rencontre lors de la conception de réseaux sans fil. Nous montrons que le problème est NP-difficile, même quand la couverture et la connexité proviennent d’un ensemble de disques unité dans le plan. Pour ce cas particulier, nous montrons que choisir de manière gloutonne deux disques qui maximisent le gain marginal tout en maintenant la solution connexe réalise une 2-approximation. Nous améliorons ce ratio d’approximation en donnant un schéma d’approximation en temps polynomial avec une légère augmentation de ressource, basé sur la technique d’Arora pour le voyageur de commerce euclidien. Dans la deuxième partie de cette thèse, on se concentre sur le problème du stable maximum. Une approche naturelle est de successivement choisir un sommet de degré minimum, le placer dans la solution en construction, puis le retirer avec ses voisins du graphe. Nous présentons une nouvelle technique pour analyser la performance de cette approche gloutonne dans différentes classes de graphes et abordons la question suivante : s’il y a plusieurs sommets de degré minimum, lequel l’algorithme devrait-il choisir pour maximiser la taille de la solution finale ? Avec cet outil, nous concevons une règle pour briser les cas d’égalité, qui conduit à la meilleure approximation possible dans les graphes sous-cubiques et pour ce type d’algorithmes gloutons. Nous complémentons ces résultats par des résultats négatifs qui suggèrent que la conception de bonnes règles brisant les cas d’égalité est une tâche difficile. La troisième et dernière partie de la thèse est consacrée au problème du multiflot entier maximum. Ce problème est difficile et a été très étudié. Par exemple, une approximation de facteur constant est probablement impossible même quand le graphe d’offre est planaire et cubique. Dans le cas particulier où le graphe d’offre et les arêtes de demande forment ensemble un graphe de genre borné, nous présentons un algorithme avec un facteur d’approximation constant. L’algorithme consiste en une succession de procédures gloutonnes qui exploitent les propriétés topologiques des graphes et des lacets sur des surfaces.

The contributions of this thesis work are two fold. The first part deals with the study of local defects in crystalline materials. Chapter 1 gives a brief overview of the main models used in quantum chemistry for electronic structure calculations. In Chapter 2, an exact variational model for the description of local defects in a periodic crystal in the framework of the Thomas-Fermi-von Weisz"acker theory is presented. It is justified by means of thermodynamic limit arguments. In particular, it is proved that the defects modeled within this theory are necessarily neutrally charged. Chapters 3 and 4 are concerned with the so-called spectral pollution phenomenon. Indeed, when an operator is discretized, spurious eigenvalues which do not belong to the spectrum of the initial operator may appear. In Chapter 3, we prove that standard Galerkin methods with finite elements discretization for the approximation of perturbed periodic Schrödinger operators are prone to spectral pollution. Besides, the eigenvectors associated with spurious eigenvalues can be characterized as surface states. It is possible to circumvent this problem by using augmented finite element spaces, constructed with the Wannier functions of the periodic unperturbed Schr"odinger operator. We also prove that the supercell method, which consists in imposing periodic boundary conditions on a large simulation domain containing the defect, does not produce spectral pollution. In Chapter 4, we give a priori error estimates for the supercell method. It is proved in particular that the rate of convergence of the method scales exponentiall with respect to the size of the supercell. The second part of this thesis is devoted to the study of greedy algorithms for the resolution of high-dimensional uncertainty quantification problems. Chapter 5 presents the most classical numerical methods used in the field of uncertainty quantification and an introduction to greedy algorithms. In Chapter 6, we prove that these algorithms can be applied to the minimization of strongly convex nonlinear energy functionals and that their convergence rate is exponential in the finite-dimensional case. We illustrate these results on obstacle problems with uncertainty via penalized formulations, Ce travail comporte deux volets. Le premier concerne l'étude de défauts locaux dans des matériaux cristallins. Le chapitre 1 donne un bref panorama des principaux modèles utilisés en chimie quantique pour le calcul de structures électroniques. Dans le chapitre 2, nous présentons un modèle variationnel exact qui permet de décrire les défauts locaux d'un cristal périodique dans le cadre de la théorie de Thomas-Fermi-von Weiszäcker. Celui-ci est justifié à l'aide d'arguments de limite thermodynamique. On montre en particulier que les défauts modélisés par cette théorie ne peuvent pas être chargés électriquement. Les chapitres 3 et 4 de cette thèse traitent du phénomène de pollution spectrale. En effet, lorsqu'un opérateur est discrétisé, il peut apparaître des valeurs propres parasites, qui n'appartiennent pas au spectre de l'opérateur initial. Dans le chapitre 3, nous montrons que des méthodes d'approximation de Galerkin via une discrétisation en éléments finis pour approcher le spectre d'opérateurs de Schrödinger périodiques perturbés sont sujettes au phénomène de pollution spectrale. Par ailleurs, les vecteurs propres associés aux valeurs propres parasites peuvent être interprétés comme des états de surface. Nous prouvons qu'il est possible d'éviter ce problème en utilisant des espaces d'éléments finis augmentés, construits à partir des fonctions de Wannier associées à l'opérateur de Schrödinger périodique non perturbé. On montre également que la méthode dite de supercellule, qui consiste à imposer des conditions limites périodiques sur un domaine de simulation contenant le défaut, ne produit pas de pollution spectrale. Dans le chapitre 4, nous établissons des estimations d'erreur a priori pour la méthode de supercellule. En particulier, nous montrons que l'erreur effectuée décroît exponentiellement vite en fonction de la taille de la supercellule considérée. Un deuxième volet concerne l'étude d'algorithmes gloutons pour résoudre des problèmes de propagation d'incertitudes en grande dimension. Le chapitre 5 de cette thèse présente une introduction aux méthodes numériques classiques utilisées dans le domaine de la propagation d'incertitudes, ainsi qu'aux algorithmes gloutons. Dans le chapitre 6, nous prouvons que ces algorithmes peuvent être appliqués à la minimisation de fonctionnelles d'énergie fortement convexes non linéaires et que leur vitesse de convergence est exponentielle en dimension finie. Nous illustrons ces résultats par la résolution de problèmes de l'obstacle avec incertitudes via une formulation pénalisée

The contributions of this thesis work are two fold. The first part deals with the study of local defects in crystalline materials. Chapter 1 gives a brief overview of the main models used in quantum chemistry for electronic structure calculations. In Chapter 2, an exact variational model for the description of local defects in a periodic crystal in the framework of the Thomas-Fermi-von Weisz"acker theory is presented. It is justified by means of thermodynamic limit arguments. In particular, it is proved that the defects modeled within this theory are necessarily neutrally charged. Chapters 3 and 4 are concerned with the so-called spectral pollution phenomenon. Indeed, when an operator is discretized, spurious eigenvalues which do not belong to the spectrum of the initial operator may appear. In Chapter 3, we prove that standard Galerkin methods with finite elements discretization for the approximation of perturbed periodic Schrödinger operators are prone to spectral pollution. Besides, the eigenvectors associated with spurious eigenvalues can be characterized as surface states. It is possible to circumvent this problem by using augmented finite element spaces, constructed with the Wannier functions of the periodic unperturbed Schr"odinger operator. We also prove that the supercell method, which consists in imposing periodic boundary conditions on a large simulation domain containing the defect, does not produce spectral pollution. In Chapter 4, we give a priori error estimates for the supercell method. It is proved in particular that the rate of convergence of the method scales exponentiall with respect to the size of the supercell. The second part of this thesis is devoted to the study of greedy algorithms for the resolution of high-dimensional uncertainty quantification problems. Chapter 5 presents the most classical numerical methods used in the field of uncertainty quantification and an introduction to greedy algorithms. In Chapter 6, we prove that these algorithms can be applied to the minimization of strongly convex nonlinear energy functionals and that their convergence rate is exponential in the finite-dimensional case. We illustrate these results on obstacle problems with uncertainty via penalized formulations, Ce travail comporte deux volets. Le premier concerne l'étude de défauts locaux dans des matériaux cristallins. Le chapitre 1 donne un bref panorama des principaux modèles utilisés en chimie quantique pour le calcul de structures électroniques. Dans le chapitre 2, nous présentons un modèle variationnel exact qui permet de décrire les défauts locaux d'un cristal périodique dans le cadre de la théorie de Thomas-Fermi-von Weiszäcker. Celui-ci est justifié à l'aide d'arguments de limite thermodynamique. On montre en particulier que les défauts modélisés par cette théorie ne peuvent pas être chargés électriquement. Les chapitres 3 et 4 de cette thèse traitent du phénomène de pollution spectrale. En effet, lorsqu'un opérateur est discrétisé, il peut apparaître des valeurs propres parasites, qui n'appartiennent pas au spectre de l'opérateur initial. Dans le chapitre 3, nous montrons que des méthodes d'approximation de Galerkin via une discrétisation en éléments finis pour approcher le spectre d'opérateurs de Schrödinger périodiques perturbés sont sujettes au phénomène de pollution spectrale. Par ailleurs, les vecteurs propres associés aux valeurs propres parasites peuvent être interprétés comme des états de surface. Nous prouvons qu'il est possible d'éviter ce problème en utilisant des espaces d'éléments finis augmentés, construits à partir des fonctions de Wannier associées à l'opérateur de Schrödinger périodique non perturbé. On montre également que la méthode dite de supercellule, qui consiste à imposer des conditions limites périodiques sur un domaine de simulation contenant le défaut, ne produit pas de pollution spectrale. Dans le chapitre 4, nous établissons des estimations d'erreur a priori pour la méthode de supercellule. En particulier, nous montrons que l'erreur effectuée décroît exponentiellement vite en fonction de la taille de la supercellule considérée. Un deuxième volet concerne l'étude d'algorithmes gloutons pour résoudre des problèmes de propagation d'incertitudes en grande dimension. Le chapitre 5 de cette thèse présente une introduction aux méthodes numériques classiques utilisées dans le domaine de la propagation d'incertitudes, ainsi qu'aux algorithmes gloutons. Dans le chapitre 6, nous prouvons que ces algorithmes peuvent être appliqués à la minimisation de fonctionnelles d'énergie fortement convexes non linéaires et que leur vitesse de convergence est exponentielle en dimension finie. Nous illustrons ces résultats par la résolution de problèmes de l'obstacle avec incertitudes via une formulation pénalisée