I'm looking for [concise, yet comprehensive] online resources and/or (state of the art) survey papers presenting complexity results for classical OR problems such as
(and their respective variants).
By "complexity results", both problem-specific lower bounds (resp., complexity classes) as well as performance of seminal algorithms (optimal, approximative) should be addressed.
For instance, the Scheduling Zoo is a nice searchable bibliography on results w.r.t. scheduling problems (though, it does not offer detailed statements in terms of Big-\(O\)-assessments).
Collected web resources:
PS: This is a "community question". Feel free to edit as needed. (That is, if you have at least 30 "karma points".)
This question is marked "community wiki".
This one is a classic resource for NP-hard problems: http://www.csc.kth.se/~viggo/wwwcompendium/. Unfortunately, it does not seem to get updated any more, but there are probably too many results out there to keep track.
This answer is marked "community wiki".
answered 30 Sep '10, 08:32