0
$\begingroup$

I came cross some works try to use deep learning to approximate NP-Hard

https://arxiv.org/pdf/1810.10659.pdf

Though the paper seems to have very good results but based on the citations. I'm quit doubt if it really the state of art approximation for NP-hard problem.

I'm wondering what are some state of art NP-Hard approximation algorithms for each problems ?

Improve this question
$\endgroup$
5
  • $\begingroup$ You're asking for a summary of a huge and expanding field of research. An answer to this question could easily be a survey paper or even a whole book. $\endgroup$
    – David Richerby
    Commented May 25, 2019 at 10:39
  • $\begingroup$ @DavidRicherby. Is there any survey paper or book recently published ? $\endgroup$
    – ElleryL
    Commented May 25, 2019 at 21:06
  • $\begingroup$ please look at this page: nada.kth.se/~viggo/problemlist/compendium.html it has many and many results about both lower and upper bound with all resources (including survey) for each problems in NP-hard as far as I know. It looks like Complexity Zoo in complexity classes. I recommend it. $\endgroup$
    – YOUSEFY
    Commented Jun 10, 2019 at 18:30
  • $\begingroup$ @YOUSEFY; this is great ! Thanks ! $\endgroup$
    – ElleryL
    Commented Jun 11, 2019 at 19:08
  • $\begingroup$ @YOUSEFY It's a good resource, but far from comprehensive (indeed, that's next to impossible). $\endgroup$
    – Juho
    Commented Jun 12, 2019 at 4:10

1 Answer 1

Reset to default
1
$\begingroup$

First, there are two aspects to separate here: theoretical approximation and practical approximation (i.e., heuristics). With heuristics, such as in the NIPS paper you mention, the goal is roughly to propose some method, take a large bunch of actual instances of a problem, benchmark empirically the method, and draw conclusions as to how well we did in terms of approximation.

This is in contrast to (theoretical) approximation algorithms that give a formal guarantee on solution quality, on all possible instances. For example, the guarantee could be "the solution returned by this algorithm is either optimal or at most three less than the optimal". But as you might know, there is an enormous amount of hard problems that can be wildly different in terms of approximation. Maximum clique or chromatic number, for instance, are very hard to approximate theoretically.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the clarification. I'm wondering if there is a relatively new survey or review paper or even book on either of two aspects ? $\endgroup$
    – ElleryL
    Commented May 26, 2019 at 19:15
  • $\begingroup$ @ElleryL Williamsons & Shmoys is a solid book for approximation as is Vazirani. $\endgroup$
    – Juho
    Commented May 26, 2019 at 19:25

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