Where to find info on (polytime) approximability of various discrete optimization problems?
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/