Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio?

Any research that compares algorithms using smoothed analysis would be interesting (e.g. algorithms that have the same worst-case time complexity).

  • 2
    $\begingroup$ My question (cstheory.stackexchange.com/q/40816/17591) on theoretically hard problems solvable in practice seems to be in the same vein. I don't specifically limit the question to Smoothed Analysis, but some of the answers there might be relevant. Also, you may want to extend the question there too. $\endgroup$ May 24, 2018 at 0:18

1 Answer 1


As far as I am aware, a comparison of approximation algorithms has not been done so far with respect to smoothed analysis. There are only a few papers on smoothed analysis of approximation ratios in the first place.

Maybe only loosely related: bijective analysis has been used to directly compare the competitive ratio of online algorithms (Angelopoulos, Schweitzer, "Paging and List Update under Bijective Analysis", J. ACM, 2013).

See also here for more about smoothed analysis of approximation algorithms: "Smoothed analysis of approximation algorithms".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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