El análisis suavizado se ha aplicado muchas veces para comprender el tiempo de ejecución de algoritmos exactos para muchos problemas como la programación lineal y k-means. Hay resultados bastante generales en este ámbito, por ejemplo, Heiko Röglin y Berthold Vöcking, Análisis suavizado de la programación de enteros , 2005. Algunos de estos resultados generales parecen basarse en lemas de aislamiento para producir una instancia con una solución óptima única. Suponiendo que , este documento descarta la existencia de algoritmos de tiempo polinomiales suavizados para problemas de N P -duro.
Se han realizado algunos trabajos sobre análisis suavizado para proporciones de algoritmos de aproximación. Existe Rao Raghavendra, Probabilistic and Smoothhed Analysis of Approximation Algorithms , 2008, que intenta dar un límite de aproximación mejorado para el algoritmo Christofides con análisis suavizado. Sin embargo, no se da una relación de aproximación explícita.