# Smoothed analysis of approximation algorithms

Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for example Heiko Röglin and Berthold Vöcking, Smoothed analysis of integer programming, 2005. Some of these general results seem to rely on isolation lemmas in order to produce an instance with a unique optimal solution. Assuming $$\mathsf{NP}\ne \mathsf{ZPP}$$, this paper rules out the existence of smoothed polynomial time algorithms for $$\mathsf{NP}$$-hard problems.

Some work has been done on smoothed analysis for approximation algorithm ratios. There is Rao Raghavendra, Probabilistic and Smoothed Analysis of Approximation Algorithms, 2008 which attempts to give an improved approximation bound for the Christofides algorithm with smoothed analysis. No explicit approximation ratio is given, though.