10
$\begingroup$

Everyone knows "Garey & Johnson", which is my go-to reference whenever I need a problem to transform from for an NP-hardness proof. However I recently find myself in need of an APX-hardness proof, and I wonder if there is a similar (and more up to date..?) collection of problems that have been shown to be APX-hard.

Does anybody know of anything like this? I find it hard to believe that there is no website systematically collecting such problems, but my Google skills seem to be insufficient.

Improve this question
$\endgroup$
5
$\begingroup$

I've used this compendium a few times... Is this what you were aiming for?

Improve this answer
$\endgroup$
3
  • $\begingroup$ That is already very nice, thank you! However, the optimum would be something even more comprehensive, and searchable for APX-hardness... I'll see if anything else pops up. $\endgroup$ – Lukas Barth Aug 11 '16 at 15:23
  • 1
    $\begingroup$ Can you provide any citation information that will help find this information if the link stops working? We want answers to remain useful even if the link stops working (and we'd prefer not to be just a link farm). $\endgroup$ – D.W.♦ Aug 11 '16 at 21:29
  • $\begingroup$ It looks like this collection is part of a book, namely: Ausiello, Giorgio, et al. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012. springer.com/us/book/9783540654315 DOI: 10.1007/978-3-642-58412-1 $\endgroup$ – Lukas Barth Aug 19 '16 at 12:15

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.