A note on probably certifiably correct algorithms - 24/02/16
pages | 5 |
Iconographies | 0 |
Vidéos | 0 |
Autres | 0 |
Abstract |
Many optimization problems of interest are known to be intractable, and while there are often heuristics that are known to work on typical instances, it is usually not easy to determine a posteriori whether the optimal solution was found. In this short note, we discuss algorithms that not only solve the problem on typical instances, but also provide a posteriori certificates of optimality, probably certifiably correct (PCC) algorithms. As an illustrative example, we present a fast PCC algorithm for minimum bisection under the stochastic block model and briefly discuss other examples.
Le texte complet de cet article est disponible en PDF.Résumé |
De nombreux problèmes d'optimisation, bien qu'ils soient difficiles à traiter dans les cas les plus compliqués, peuvent souvent être résolus de manière efficace par des heuristiques lorsque les données du problème sont tirées au hasard (données typiques). Malheureusement, dans la plupart des cas, on ne sait que rarement certifier si l'heuristique produit une solution optimale au problème. Dans cette note, nous décrivons une famille d'algorithmes qui non seulement résolvent le problème sur des données typiques, mais aussi produisent un certificat d'optimalité. À titre d'illustration, nous décrivons un tel algorithme pour le problème du partitionnement de graphe dans le modele stochastique à blocs. D'autres exemples sont aussi discutés brièvement.
Le texte complet de cet article est disponible en PDF.Plan
Vol 354 - N° 3
P. 329-333 - mars 2016 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?