Analyse lissée des algorithmes d'approximation

L'analyse lissée a été appliquée à plusieurs reprises pour comprendre le temps d'exécution d'algorithmes exacts pour de nombreux problèmes comme la programmation linéaire et les k-means. Il existe des résultats assez généraux dans ce domaine, par exemple Heiko Röglin et Berthold Vöcking, Smoothed analysis of integer programming , 2005. Certains de ces résultats généraux semblent s'appuyer sur des lemmes d'isolement afin de produire une instance avec une solution optimale unique. En supposant que , cet article exclut l'existence d'algorithmes de temps polynomiaux lissés pour les problèmes durs.$\mathsf{NP}\ne \mathsf{ZPP}$$\mathsf{NP}$

Certains travaux ont été effectués sur l'analyse lissée des rapports d'algorithmes d'approximation. Il y a Rao Raghavendra, Probabilistic and Smoothed Analysis of Approximation Algorithms , 2008 qui tente de donner une approximation améliorée pour l'algorithme Christofides avec une analyse lissée. Cependant, aucun rapport d'approximation explicite n'est donné.

Y a-t-il une raison pour laquelle la dureté des résultats d'approximation devrait limiter les rapports d'approximation des algorithmes qui s'exécutent en temps polynomial lissé? Les résultats de l'article de Heiko Röglin et Berthold Vöcking s'appliquent-ils également aux algorithmes d'approximation?

L'article de Bläser, Panagiotou et Rao traite de la concentration de la tournée produite par l'algorithme de Christofides. Aucun rapport d'approximation de cas moyen n'est revendiqué, à l'exception de certains résultats expérimentaux.

L'article de Röglin et Vöcking (Math. Program., 2007) et un article antérieur de Beier et Vöcking (SIAM J. Comput., 2006) indiquent en gros que le temps polynomial lissé est équivalent au temps pseudo-polynomial randomisé. Ici, pseudo-polynôme signifie polynôme à temps d'exécution dans la taille d'entrée et l'amplitude des coefficients qui sont perturbés. Cela exclut la complexité polynomiale lissée pour les problèmes d'optimisation fortement NP-durs (sauf NP = ZPP).

En ce qui concerne l'analyse et l'approximation lissées, il n'y a que très peu d'articles qui traitent de problèmes ou d'algorithmes spécifiques (Englert, Röglin et Vöcking pour l'heuristique 2-opt pour TSP; Bläser, Manthey et Rao ainsi que Curticapean et Künnemann pour l'heuristique de partitionnement; Karger et Onak pour l'emballage multidimensionnel). Cependant, je ne connais aucun lien structurel entre l'inapproximabilité et l'analyse lissée.