<p>The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: <a href="http://www.csc.kth.se/%7Eviggo/problemlist/" rel="nofollow noreferrer">http://www.csc.kth.se/~viggo/problemlist/</a></p>

CC BY-SA 4.0
2020-07-20T06:28:44.410Z
2020-07-20T06:28:44.410Z
Hermann Gruber
<p>The compendium from Crescenzi is the most complete that I am aware of, despite being pretty old now. You can also watch this more recent (still twelve years old) survey:</p>
<p>Vangelis Paschos.  An overview on polynomial approximation of NP-hard problems.
<a href="https://hal.archives-ouvertes.fr/hal-00186549/document" rel="nofollow noreferrer">https://hal.archives-ouvertes.fr/hal-00186549/document</a></p>

CC BY-SA 4.0
2020-07-21T17:00:51.777Z
2020-07-21T17:00:51.777Z
Nicolas GZ
<p>Where to find info on (polytime) approximability of  various discrete optimization problems?</p>
<p>Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of various optimization problems?</p>

<reference-request><co.combinatorics><approximation-algorithms><optimization><approximation-hardness>
Where to find info on (polytime) approximability of various discrete optimization problems?
user122938
# Where to find info on (polytime) approximability of various discrete optimization problems?

(Asked by: username_0 on 2020-07-20)

Where to find info on (polytime) approximability of various discrete optimization problems?

Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of various optimization problems?

**Tags:** reference-request, co.combinatorics, approximation-algorithms, optimization, approximation-hardness


---

## 2 answers

### Answer by username_1 on 2020-07-20. Score: 4

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: [http://www.csc.kth.se/~viggo/problemlist/](http://www.csc.kth.se/%7Eviggo/problemlist/)


---

### Answer by username_2 on 2020-07-21. Score: 0

The compendium from Crescenzi is the most complete that I am aware of, despite being pretty old now. You can also watch this more recent (still twelve years old) survey:

Vangelis Paschos. An overview on polynomial approximation of NP-hard problems.
<https://hal.archives-ouvertes.fr/hal-00186549/document>


---

