4
$\begingroup$

A paper published in SODA this year (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

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Dec 16 '19 at 20:34
  • 2
    $\begingroup$ 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. $\endgroup$ – Yonatan N Dec 17 '19 at 0:24
  • 3
    $\begingroup$ 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. $\endgroup$ – pschill Dec 17 '19 at 9:22
  • 2
    $\begingroup$ 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? $\endgroup$ – Clement C. Dec 18 '19 at 7:59
  • $\begingroup$ (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.) $\endgroup$ – Clement C. Dec 18 '19 at 8:02
6
$\begingroup$

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:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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