0
$\begingroup$

I usually check the NP-compendium from Pierluigi Crescenzi, and Viggo Kann when I want to know the APX status and approximability results of a problem.

However, I understand that maintaining it is a lot of work, which explains why it is not up to date in some cases. By not up to date, I do not mean non-exhaustive, but that better results on some problems are not included.

Does anyone know an equivalent and more specific website focused only on approximation, which would be more up to date ?

I am not really asking the same question as this one, or this one, but I understand that they may bring the same answer.

Remark: The last example I found was on the Minimum Steiner Tree with distance 1 and 2 on complete graphs, which is said to be approximable in 1.28, but there is a paper from 2009 which provides a 1.25 ratio. It may have been updated.

$\endgroup$
1
  • 2
    $\begingroup$ No, unfortunately there is no such page. It is indeed too much work to keep it up to date. You still have to rely on the usual methods. $\endgroup$
    – Juho
    Commented Jan 28, 2020 at 17:24

1 Answer 1

3
$\begingroup$

You're expecting too much to expect there to be a single web page that is somehow always updated with the latest in the research literature on the subject.

Let me teach you how to figure out this information for yourself, instead of relying on someone else to have done it for you. The general approach is to find one paper on the approximability of your problem; then use Google Scholar to track down related papers.

How do you find one paper on the problem? Perhaps that web page will show you one, even if it's not the latest on the topic. Perhaps you can search using Google Scholar to find such a paper. Perhaps you'll have to try other methods.

Then, how do you find other papers on the subject, to find what is the latest and greatest state of the art? Read the introduction and related work section of that paper, and it should give you an entryway into previous results. Also, search for that paper on Google Scholar and find what papers cite it; that should give you an entryway into newer results, and you can scan the title and abstracts of those papers to see if they are relevant. Then, proceed recursively from each paper you've determined to be relevant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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