Graph partitioning is a fundamental optimization problem that has been intensively studied. Many graph partitioning formulations are important as building blocks for divide-and-conquer algorithms on graphs as well as to many applications such as VLSI layout, packet routing in distributed networks, clustering and image segmentation. Unfortunately such problems are notorious for the huge gap between known best known approximation algorithms and hardness of approximation results. In this thesis, we study approximation algorithms for graph partitioning problems using a strong hierarchy of relaxations based on semi-definite programming, called Lasserre Hierachy. Our main contribution in this thesis is a propagation based rounding framework for solutions arising from such relaxations. We present a novel connection between the quality of solutions it outputs and column based matrix reconstruction problem. As part of our work, we derive optimal bounds on the number of columns necessary together with efficient randomized and deterministic algorithms to find such columns. Using this framework, we derive approximation schemes for many graph partitioning problems with running times dependent on how fast the graph spectrum grows. Our final contribution is a fast SDP solver for this rounding framework: Even though SDP relaxation has nO(r) many variables, we achieve running times of the form 2O(r) poly(n) by only partially solving the relevant part of relaxation. In order to achieve this, we present a new ellipsoid algorithm that returns certificate of infeasibility.

Les gestionnaires des réseaux de transport d'électricité doivent adapter leurs outils d'aide à la décision aux avancées technologiques du XXIième siècle. Une opération sous-jacente à beaucoup d'outils est de calculer les flux en actif/réactif qui minimisent les pertes ou les coûts de production. Mathématiquement, il s'agit d'un problème d'optimisation qui peut être décrit en utilisant seulement l'addition et la multiplication de nombres complexes. L'objectif de cette thèse est de trouver des solutions globales. Un des aboutissements de ce projet doctoral hautement collaboratif est d'utiliser des résultats récents en géométrie algébrique pour calculer des flux optimaux dans le réseau Européen à haute tension. / Transmission system operators need to adapt their decision-making tools to the technological evolutions of the twenty first century. A computation inherent to most tools seeks to find alternating-current power flows that minimize power loss or generation cost. Mathematically, it consists in an optimization problem that can be described using only addition and multiplication of complex numbers. The objective of this thesis is to find global solutions, in other words the best solutions to the problem. One of the outcomes of this highly collaborative doctoral project is to use recent results from algebraic geometry to compute globally optimal power flows in the European high-voltage transmission network.