Programmation Linéaire, Complexité: Séparation Et Optimisation (Math #38)

Description

Le but de cet ouvrage est de faire une pr sentation compl te et auto contenue de l' quivalence entre les Oracles S parer, Optimiser et Appartenir en Optimisation Poly drale. Dans ce but le livre commence par une pr sentation d taill e des probl mes de Complexit des Algorithmes suivi d'une pr sentation de la m thode du Simplexe. On d crit ensuite l'algorithme de Khachiyan sans luder les probl mes num riques. Viennent alors une suite d'algorithmes polynomiaux pour Optimiser partir de l'oracle S parer. Apr's quelques transformations, on montre que, par polarit , on peut S parer partir de l'oracle Optimiser. La premi re quivalence est revue apr's avoir d crit l'algorithme LLL. L'ouvrage se termine par la r duction de S parer Appartenir.