<p>A very good question! While I think a feasible solution which is 4000 times worse than the optimum is often not very practical, if you have several approximation algorithms to choose from, I would rather implement the one with a better performance guarantee. Well, maybe not always. At the very least, the feasible solutions found are often of much better quality than the guarantee. That is, if an algorithm performs better than terribly in the worst case, it often performs very well in practice. At least I've read something along those lines.</p>

<p>Apart from that, you can think of the result as a mathematical theorem, which may be of interest in its own right. Citing the wikipedia article on <a href="https://en.m.wikipedia.org/wiki/Approximation_algorithm" rel="nofollow noreferrer">approximation algorithm</a>: </p>

<blockquote>
  <p>The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the Goemans-Williamson algorithm for Maximum Cut which solves a graph theoretic problem using high dimensional geometry.</p>
</blockquote>

CC BY-SA 4.0
2019-12-16T20:40:13.147Z
2020-01-12T07:37:48.723Z
2020-01-12T07:37:48.723Z
Hermann Gruber
<p>A <a href="https://dl.acm.org/citation.cfm?id=3310573" rel="nofollow noreferrer">paper published in SODA this year</a> (2019) proposed a constant approximation algorithm for the lower bounded facility location problem with general lower bounds.</p>

<p>To my surprise, when reading the paper, I verified that its constant approximation factor is 4000.</p>

<p>Therefore, I was left wondering if this algorithm is really useful for something.<br>
Like, do you know, a solution that is 4000 times worse than the optimal solution can be anything, and probably a solution given by a simple polynomial-time greedy algorithm will be better than that of given by this more complex approximation algorithm.</p>

<hr>

<p><a href="https://i.sstatic.net/rA5Dv.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rA5Dv.jpg" alt="Photo of the theorem"></a></p>

CC BY-SA 4.0
2019-12-16T20:34:11.760Z
A polynomial time algorithm that runs in $n^{100}$ time is not very practical but reveals something interesting about the problem if no previous polynomial-time algorithm was known. Same thing with approximation ratio. This is the usual theory fare where most of the papers are really for insiders to make sense of problems/techniques etc.
Chandra Chekuri
CC BY-SA 4.0
2019-12-17T00:24:51.260Z
Another way to view such results is as limits of what kinds of hardness results one can hope to attain. In particular, the cited result for LBFL shows that no $\omega(1)$-hardness result is possible, so any attempted construction that would get such a result is necessarily flawed.
Yonatan N
CC BY-SA 4.0
2019-12-17T09:22:13.037Z
I just typed *number of atoms in the universe* into my search bar and got the answer *between $10^{78}$ and $10^{82}$*. This is a difference of factor 10'000, but I still found the answer to be helpful.
pschill
CC BY-SA 4.0
2019-12-18T07:59:42.197Z
Another point not mentioned in the current answer: there is a difference between "the authors proved an approximation factor of 4000" and "the algorithm actually could be shown to have an approximation factor of say 10, if one were to spend an insane amount of time and energy in tightening the arguments and keeping track of all the steps very carefully." (*this may not necessarily be the case here, but often is*). Ask yourself: between a 20-page paper showing the former, and a 100-page paper showing the latter *with the same exact ideas and arguments*, which reader would ever read the 2nd?
Clement C.
CC BY-SA 4.0
2019-12-18T08:02:07.817Z
(I.e., if the goal is to go for instance from an $O(\log n)$-approximation to a new, hitherto unknown $O(1)$-approximation, getting a small constant is nice, indeed, but not having scores of very technical pages just making sure no factor $2$ is lost at any step, thus making the paper unreadable... is nicer.)
Clement C.
CC BY-SA 4.0
2019-12-18T12:09:58.103Z
This paper uses a same argument. The authors argue that this algorithm can be stretched until holding an approximation factor of 100. However, I agree you you, @ClementC., this will probably make the paper unreadable
Iago Carvalho
<approximation-algorithms><approximation>
Is an algorithm with an approximation factor of 4000 useful?
Iago Carvalho
# Is an algorithm with an approximation factor of 4000 useful?

(Asked by: username_0 on 2019-12-16)

A [paper published in SODA this year](https://dl.acm.org/citation.cfm?id=3310573) (2019) proposed a constant approximation algorithm for the lower bounded facility location problem with general lower bounds.

To my surprise, when reading the paper, I verified that its constant approximation factor is 4000.

Therefore, I was left wondering if this algorithm is really useful for something.  
Like, do you know, a solution that is 4000 times worse than the optimal solution can be anything, and probably a solution given by a simple polynomial-time greedy algorithm will be better than that of given by this more complex approximation algorithm.

---

[![Photo of the theorem](https://i.sstatic.net/rA5Dv.jpg)](https://i.sstatic.net/rA5Dv.jpg)

**Tags:** approximation-algorithms, approximation
> **Comments:**
> **username_1**: A polynomial time algorithm that runs in $n^{100}$ time is not very practical but reveals something interesting about the problem if no previous polynomial-time algorithm was known. Same thing with approximation ratio. This is the usual theory fare where most of the papers are really for insiders to make sense of problems/techniques etc.  
> **username_2**: Another way to view such results is as limits of what kinds of hardness results one can hope to attain. In particular, the cited result for LBFL shows that no $\omega(1)$-hardness result is possible, so any attempted construction that would get such a result is necessarily flawed.  
> **username_3**: I just typed *number of atoms in the universe* into my search bar and got the answer *between $10^{78}$ and $10^{82}$*. This is a difference of factor 10'000, but I still found the answer to be helpful.  
> **username_4**: Another point not mentioned in the current answer: there is a difference between "the authors proved an approximation factor of 4000" and "the algorithm actually could be shown to have an approximation factor of say 10, if one were to spend an insane amount of time and energy in tightening the arguments and keeping track of all the steps very carefully." (*this may not necessarily be the case here, but often is*). Ask yourself: between a 20-page paper showing the former, and a 100-page paper showing the latter *with the same exact ideas and arguments*, which reader would ever read the 2nd?  
> **username_4**: (I.e., if the goal is to go for instance from an $O(\log n)$-approximation to a new, hitherto unknown $O(1)$-approximation, getting a small constant is nice, indeed, but not having scores of very technical pages just making sure no factor $2$ is lost at any step, thus making the paper unreadable... is nicer.)  
> **username_0**: This paper uses a same argument. The authors argue that this algorithm can be stretched until holding an approximation factor of 100. However, I agree you you, @ClementC., this will probably make the paper unreadable  

---

## 1 answers

### Answer by username_5 on 2019-12-16. Score: 6 | Accepted answer

A very good question! While I think a feasible solution which is 4000 times worse than the optimum is often not very practical, if you have several approximation algorithms to choose from, I would rather implement the one with a better performance guarantee. Well, maybe not always. At the very least, the feasible solutions found are often of much better quality than the guarantee. That is, if an algorithm performs better than terribly in the worst case, it often performs very well in practice. At least I've read something along those lines.

Apart from that, you can think of the result as a mathematical theorem, which may be of interest in its own right. Citing the wikipedia article on [approximation algorithm](https://en.m.wikipedia.org/wiki/Approximation_algorithm):

> The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the Goemans-Williamson algorithm for Maximum Cut which solves a graph theoretic problem using high dimensional geometry.


---

