This is based on lecture notes I took together with Sebastian Steenbruck in 2010.

In this series of posts I’ll talk about Approximation Algorithms and Linear Programming and how the two relate to each other. You will need some linear algebra to understand everything. There are exercises in the text which you should probably do. Most are pretty simple and should be doable in less than 15 minutes.

The following pages make heavy use of MathML to render math. It looks fine in Firefox and Safari on my machine, but MathML is not particularly well supported in Browsers. Chrome and Internet Explorer will not display it correctly, I think. But since I like browsing without Javascript, MathML seems to be the only way to get math on my page.

- Introduction
- Solving Linear Programs