7

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).

Andrius Vaicenavicius
  • 91
  • 5
  • 2
    My question (https://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. – Konstantinos Koiliaris May 24 '18 at 00:18

1 Answers1

3

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".

Bodo Manthey
  • 345
  • 3
  • 10