Search

Convex optimization has been a powerful tool for designing algorithms. In practice is a widely used in areas such as operations research and machine learning, but also in many fundamental combinatorial problems they yield to the best know approximations algorithms providing unconditional guarantees over the solution quality. In the first part of this work we study the effect of constructing convex relaxations to a packing problem, based on applying lift & project methods. We exhibit a weakness of this relaxations when they are obtained from the natural formulations of this problem, by showing the impossibility of reducing the gap even when this relaxations are very large. We provide a way of combining symmetry breaking procedures and lift & project methods to obtain arbitrarily good gaps. In the second part of this thesis we study online selection problems, that is, elements arrive over time and we have to select some of them, irrevocably, in order to meet some combinatorial constraints, but also trying to maximize the quality of the selection. Usually this quality in measured in terms of weight, but we consider a stronger variant in which weights are not necessarily known because of information availability. Instead, as long as we can rank the elements, we can provide a general framework to obtain approximation algorithms with good competitive ratios in many contexts., L'optimisation convexe a été un outil puissant pour concevoir des algorithmes. Dans la pratique est largement utilisé dans des domaines tels que la recherche opérationnelle et l'apprentissage automatique, mais aussi dans de nombreux problèmes combinatoires fondamentaux, ils cèdent aux algorithmes d'approximations les mieux connues fournissant des garanties inconditionnelles sur la qualité de la solution. Dans la première partie de ce travail, nous étudions l'effet de la construction de relaxations convexes sur un problème d'emballage, basé sur l'application de méthodes de levage et de projet. Nous montrons une faiblesse de ces relaxations lorsqu'elles sont obtenues à partir des formulations naturelles de ce problème, en montrant l'impossibilité de réduire l'écart même lorsque ces relaxations sont très importantes. Nous fournissons un moyen de combiner des procédures de rupture de symétrie et des méthodes de levage et de projet pour obtenir des écarts arbitraires. Dans la deuxième partie de cette thèse, nous étudions les problèmes de sélection en ligne, c'est-à-dire que les éléments arrivent dans le temps et nous devons en sélectionner certains irrévocablement pour répondre à certaines contraintes combinatoires, mais aussi pour maximiser la qualité de la sélection. Habituellement, cette qualité est mesurée en termes de poids, mais nous considérons une variante plus forte dans laquelle les poids ne sont pas nécessairement connus en raison de la disponibilité de l'information. Au lieu de cela, tant que nous pouvons classer les éléments, nous pouvons fournir un cadre général pour obtenir des algorithmes d'approximation avec de bons ratios compétitifs dans de nombreux contextes.