7
$\begingroup$

What kind of background in algorithms and complexity theory is needed to fully understand the computational aspects of an OR paper. To be specific, I am not always sure when a paper says 'XYZ problem is $\mathbf{NP}$ hard, or $\mathbf{NP}$ complete. etc.' or when the paper says 'XYZ algorithm performs in $\mathbf{O}$(something) or $\mathbf{\Theta}$(something) (especially in scheduling literature)'. CS/Math forums typically recommend Introduction to Algorithms by Cormen et al. (CLRS) for the same, but CLRS is a pretty dense book, and I am not sure whether should I go through the complete book, or should I pick and choose topics.

Are there any textbooks/references that I can go through (possibly without tears), to get an idea of the computational aspects that are typical to the domain of OR?

$\endgroup$
2
  • $\begingroup$ I learned from CLRS! My advice is to pick and choose topics from there it’s a great book. $\endgroup$
    – Ariel
    May 29 at 14:28
  • $\begingroup$ @Ariel can you suggest which topics should I start first? $\endgroup$
    – superhulk
    May 29 at 19:31
5
$\begingroup$

So as I mentioned in the comment CLRS is a really wonderful reference and I enjoyed learning from it in my undergraduate algorithms class. But yes, it's a big book so you probably want to pick and choose some useful topics. Here are my suggestions:

  • Ch. 2 is a fine intro to the subject, maybe skim it
  • Ch. 3 is a must and will teach you some of the asymptotic notation you mentioned.
  • Ch. 5 is good too, especially if you need to review probabilistic techniques (Ch. 9 too)

At this point, I think you probably have a handle on most of the basics so you can start to pick and choose.

For some practice of these basics, various topics on sorting in Section II may be useful.

If you are more on the computational side of OR you may need to refresh/learn data structures then Section III on data structures is very good and important to know.

I think Section IV Ch. 15 and 16 are useful for OR especially the sections on greedy algorithms. Similarly, I think Section VI on graph algorithms is also quite good and in particular Ch. 23 on spanning trees, Ch.24 and 25 on shortest paths, and Ch. 26 on flow problems. I think these topics are probably the most applicable to a lot of OR.

The last few chapters are really up to you. There are chapters on matrix operations, linear programming, approximation theory, etc. but you probably know these already and there are better and more comprehensive places to find this kind of material. You did mention NP-Completeness problems so Ch. 34 will probably be quite useful there.

If you really want to go deep on complexity theory this book is probably more advanced but also probably beyond what most OR researchers need (although it's a big field so who knows!).

Hope this helps!

$\endgroup$
1
  • 1
    $\begingroup$ This was a really informative answer. Couldn't find anything better on the internet. $\endgroup$
    – superhulk
    Jun 5 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.