Smoothed analysis of approximation algorithms

Question

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.

Is there any reason for why hardness of approximation results should limit the approximation ratios of algorithms that run in smoothed polynomial time? Do the results in Heiko Röglin and Berthold Vöcking's paper also apply for approximation algorithms?

Answer 1

The paper by Bläser, Panagiotou, and Rao deals with concentration of the tour produced by Christofides' algorithm. No average-case approximation ratio is claimed, except for some experimental results.

The paper by Röglin and Vöcking (Math. Program., 2007) and an earlier paper by Beier and Vöcking (SIAM J. Comput., 2006) roughly state that smoothed polynomial time is equivalent to randomized pseudo-polynomial time. Here, pseudo-polynomial means running-time polynomial in the input size and the magnitude of the coefficients that are perturbed. This rules out smoothed polynomial complexity for strongly NP-hard optimization problems (unless NP=ZPP).

Concerning smoothed analysis and approximation, there are only very few papers that address specific problems or algorithms (Englert, Röglin, and Vöcking for the 2-opt heuristic for TSP; Bläser, Manthey, and Rao as well as Curticapean and Künnemann for partitioning heuristics; Karger and Onak for multi-dimensional packing). However, I am not aware of any structural connections between inapproximability and smoothed analysis.