CMU Advanced Algorithms

Today's lecture, and the two lectures next week are the final three lectures of the course. Today we will do a bit more on approximation...

The deterministic integrality gap instance is super-simple: take all the d-bit strings that have at least d/2 1's in them. There are d s...

Danny lectured today on online algorithms , in particular, on ski-rental, list-update, and paging/k-server problems. Some directions to thin...

I think I was over-simplifying the proof of Fact 2 (the expected number of violated constraints by a random r-set is at most md/r, where m i...

There was a bug in problem #4b of the homework (thanks, Srivatsan): I've removed that part.

This is a vast topic dealing with the following question: you are given a convex polytope P in R^n (say, as the intersection of some halfspa...

Just to elaborate on what Yuan mentioned in class yesterday: (yet) another way to prove the integrality of the bipartite perfect matching po...