<p>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.</p>

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

<p>See also here for more about smoothed analysis of approximation algorithms: "<a href="https://cstheory.stackexchange.com/questions/17601/">Smoothed analysis of approximation algorithms</a>".</p>

CC BY-SA 4.0
2019-02-11T11:40:33.517Z
2019-02-11T11:40:33.517Z
Bodo Manthey
<p>Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio?</p>

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

CC BY-SA 4.0
2018-05-24T00:18:58.447Z
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
<ds.algorithms><approximation-algorithms><smoothed-analysis>
Smoothed analysis to compare algorithms
Andrius Vaicenavicius
# Smoothed analysis to compare algorithms

(Asked by: username_0 on 2018-05-23)

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

**Tags:** ds.algorithms, approximation-algorithms, smoothed-analysis
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2019-02-11. Score: 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](https://cstheory.stackexchange.com/questions/17601/)".


---

