• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Approximation polynomiale de problèmes d’optimisation : aspects structurels et opérationnels

Escoffier, Bruno (2005), Approximation polynomiale de problèmes d’optimisation : aspects structurels et opérationnels, doctoral thesis prepared under the supervision of Paschos, Vangelis, Université Paris Dauphine, 220 p.

View/Open
2005PA090065.pdf (1.298Mb)
Type
Thèse
Date
2005-11
Pages
220
Metadata
Show full item record
Author(s)
Escoffier, Bruno
Under the direction of
Paschos, Vangelis
Abstract (FR)
Cette thèse s'inscrit dans le domaine de l'étude des problèmes de NPO (problèmes d'optimisation dont la version décision est dans NP), et plus particulièrement dans la théorie de l'approximation polynomiale de ces problèmes. Il s'agit d'étudier la possibilité de fournir efficacement des solutions réalisables ayant une certaine qualité, qualité que nous mesurons tantôt par le rapport standard, tantôt par le rapport différentiel. Deux aspects principaux se dégagent dans notre travail : - La structure des classes d'approximation : il s'agit de structurer les classes classiques par l'introduction de réductions qui préservent certains types d'approximation et qui induisent des notions de complétude. - L'approximation polynomiale de problèmes de NPO : nous avons étudié les problèmes de la coloration pondérée, de la coloration probabiliste et de la couverture d'ensemble quadratique selon le rapport standard, ainsi que des problèmes de satisfiabilité selon le rapport différentiel.
Abstract (EN)
This thesis deals with the study of NPO-problems (optimization problems the decision version of which is in NP), and more precisely the theory of worst case polynomial approximation. In this problematic, we aim at determining how it is possible to produce efficiently a feasible solution achieving a certain quality, quality measured either by the standard ratio or by the differential ratio. Our work can be divided into two parts : - The structure of approximation classes, structure which emerges from the introduction of approximation preserving reductions which induce notions of completeness. - Polynomial approximation of some NPO problems: we studied approximation properties of the weighted coloring problem, the probabilistic coloring problem and the quadratic set covering problem using the standard ratio, and satisfiability problems using the differential ratio.
Subjects / Keywords
Complexity; Discrete Optimization; Polynomial Approximation; completeness; Complexité; optimisation discrète; complétude; approximation polynomiale

Related items

Showing items related by title and author.

  • Thumbnail
    Valeurs extrémales d'un problème d'optimisation combinatoire et approximation polynomiale 
    Demange, Marc; Paschos, Vangelis (1996) Article accepté pour publication ou publié
  • Thumbnail
    Solutions équitables approchées pour divers problèmes d’optimisation combinatoire 
    Bazgan, Cristina; Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny; Vanderpooten, Daniel (2012) Communication / Conférence
  • Thumbnail
    Quelques étapes vers la conciliation de la théorie d'approximation et celle d'optimisation : une nouvelle théorie d'approximation polynomiale et résultats préliminaires 
    Demange, Marc; Paschos, Vangelis (1993) Article accepté pour publication ou publié
  • Thumbnail
    Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation 
    Gourvès, Laurent; Escoffier, Bruno; Spanjaard, Olivier; Monnot, Jérôme (2010) Article accepté pour publication ou publié
  • Thumbnail
    Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation 
    Chopin, Morgan (2013-07) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo