Thumbnail - Request a copy

Problème du stable probabiliste

Murat, Cécile; Paschos, Vangelis (1995), Problème du stable probabiliste, Comptes Rendus de l'Académie des Sciences de Paris, 321, 4, p. 495-498

Type
Article accepté pour publication ou publié
Date
1995
Journal name
Comptes Rendus de l'Académie des Sciences de Paris
Volume
321
Number
4
Publisher
Elsevier
Pages
495-498
Metadata
Show full item record
Author(s)
Murat, Cécile
Paschos, Vangelis
Abstract (FR)
L'optimisation combinatoire probabiliste est un nouveau domaine de recherche; elle permet de mieux appréhender les problèmes concrets souvent soumis à des phénomènes aléatoires. Nous proposons dans cette Note des résultats relatifs au problème du stable probabiliste. Nous étudions deux stratégies de modification; nous montrons que la fonctionnelle associée à l'une se calcule en temps polynomial et trouvons alors la solution a priori la maximisant; après avoir donné plusieurs expressions de la fonctionnelle associée à l'autre, nous montrons que cette fonctionnelle ne peut pas être calculée en temps polynomial et en donnons un encadrement.
Subjects / Keywords
Fonctionnelle; Calculabilité; Temps polynomial; Optimisation combinatoire