I have been facinated by the extraordinary explosion in Smoothed Analysis and was struck by a assertion in the paper Smoothed Analysis of Integer Programming. This stated that Integer Linear Programming is in Smoothed P if Polynomially Bounded. This was essential true by the virtue that Integer Programming is Pseudo-polynomial!

The question therefore is:

Does this carry over to other problems universally? In particular what are the constraints?

  • 9
    $\begingroup$ Could you elaborate on what is meant by "polynomially bounded" in this context? $\endgroup$ – András Salamon Mar 23 '11 at 11:09

Integer programming is strongly NP-hard, thus integer programs can in general not be solved in pseudo-polynomial time. The result of Röglin and Vöcking is that, provided that the range of integers that the variables can assume is polynomially bounded, (randomized) pseudo-polynomial solvability is equivalent to polynomial smoothed complexity. Thus, general integer programs do not have polynomial smoothed complexity.

The statement "randomized pseudo-polynomial complexity = polynomial smoothed complexity" is not known to be true in general. For instance, the flip heuristic for Max-Cut runs in pseudo-polynomial time, but it is unknown if a local optimum w.r.t. the flip heuristic can be found with polynomial smoothed complexity (cf. Etscheid and Röglin, SODA 2014).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.