4
$\begingroup$

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

$\endgroup$
  • 1
    $\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$ – Konstantinos Koiliaris May 24 '18 at 0:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.