jump to navigation

Combinatorial Optimization May 24, 2010

Posted by CK in Research.
Tags: , , , ,

Although I’m not a huge fan of Papadimitriou’s and Steiglitz’ book, one has to appreciate the things that set this book apart from many others in the area. Looking at section 17.3 on approximation schemes, the intuitive description of the topic is excellent. Starting with the simplest definition of dynamic programming that I’ve ever encountered, and by far the best example ever (example 17.3 — why hasn’t anyone included something so clear in all the places I’ve looked?), then continuing to (F)PTAS so smoothly that one doesn’t even notice.

Bonus points for the last sentence before definition 17.3:

Such a favorable state of affairs naturally calls for a definition.

Too many “17.3” in this post.



1. Mathy Joe - May 29, 2010

What’s the definition of dynamic programming given?

Does it have anything to do with Papadimitriou’s famous class tutorial on dynamic programming?
“Step 1: write the cost of the nth step as a function of the cost of the (n-1)th step and the transition costs.”

“What’s step 2?”

“That’s step 1 of 1. You’re done.”

CK - May 30, 2010

Beautiful. But no, the definition in the book is different (actually explicitly mentioned as an *instance* of DP) :

1. Mark the node 0.

2. For j = 1, 2, …, n do:
For each marked not v mark the node u such that (v, u) \in A_j

3. Conclude that the instance has a solution iff K is marked.

2. adamo - May 30, 2010

Among other things, the book contains one of the best explanations on Simplex (or so claim Spirakis and Mavronikolas at “A glimpse at Christos H. Papadimitriou“.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: