7
1

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

  • Shortest Path and Spanning Tree Problems;
  • Network Flow, Assignment and Knapsack Problems;
  • Traveling Salesman and Vehicle Routing Problems;
  • ...

(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".

asked 29 Sep '10, 19:47

fbahr's gravatar image

fbahr ♦
3.5k313
accept rate: 11%

edited 08 Sep '13, 02:06


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.

link
This answer is marked "community wiki".

answered 30 Sep '10, 08:32

tim's gravatar image

tim
11
accept rate: 0%

Here is a very useful Library for the Quadratic Assignment Problem

http://www.seas.upenn.edu/qaplib/

Here You can find papers , solvers, solutions...

link
This answer is marked "community wiki".

answered 30 Sep '10, 12:20

Buxley's gravatar image

Buxley
534312
accept rate: 9%

edited 11 Sep '11, 10:17

Ehsan's gravatar image

Ehsan ♦
3.2k518

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×23
×8
×7

Asked: 29 Sep '10, 19:47

Seen: 1,917 times

Last updated: 08 Sep '13, 02:06

OR-Exchange! Your site for questions, answers, and announcements about operations research.