1
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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/

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

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