The greedy algorithm for facility location is by Jain, Mahdian, Markakis, Saberi, and Vazirani. The greedy augmentation step that I mentioned in the class and write about in the notes is by Mahdian, Ye and Zhang based on work by Guha and Khuller.

The max-cut algorithms are probably folk lore. We will see better algorithms later in the course using semidefinite programming. Better combinatorial algorithms for maximum directed cut can be found in this paper by Halperin and Zwick. The local search algorithms for facility location and k-median problems were studied first by Korupolu, Plaxton and Rajaraman. The factor 5 algorithm (and the factor (3+2/p) algorithm indicated in the notes, but not done in class, currently the best algorithm) for k-Median today, is due to Arya, Garg, Khandekar, Meyerson, Munagala and Pandit. Our presentation is influenced by a paper of Gupta and Tangwongsan.

My favorite reference for linear programming is the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. The ellipsoid method in all its gory details is given in this book, but I don't recommend it as bedside reading. The facility location algorithm done today is due to Shmoys, Tardos, and Aardal , and is the first constant factor approximation for it. The algorithm for generalized assignment problem (GAP) we did in class is due to Shmoys and Tardos , although they look at a minimization problem; the fact that this implies 2-approximation for the maximization version, the part which we couldn't complete due to the fire, is due to Chekuri and Khanna .

Pipage rounding was introduced by Ageev and Sviridenko and the example of max-k-coverage problem is from that paper. The algorithm to maximize submodular functions over matroid constraints can be found in full in the journal paper of Calinescu, Chekuri, Pal and Vondrak .

The SNDP result is due to Jain , although the proof of the charging argument is due to Nagarajan, Ravi, and Singh. The maximum cardinality matching in hypergraphs result, which we didn't do in class, is due to Furedi, Kahn and Seymour. This was generalized by Chan and Lau for the weighted case using an extra idea of local ratio - which we might not cover in the course. Finally, there is a monograph being written on iterative relaxations in combinatorial optimization by Lau, Ravi and Singh.

Both the 3-approximation for metric UFL and 6-approximation for k-median are from the paper by Jain and Vazirani. Primal-dual algorithms have also had a great success in network design problems - notable are the 2-approximation algorithmsfor the Steiner forest problem due to Agarwal, Klein and Ravi, and by Goemans and Williamson.

The technique of using the fractional solution as probabilistic guide to an integral solution was made concrete in the paper by Raghavan and Thomson. The facility location algorithm done in class is due to Chudak and Shmoys. The group Steiner tree algorithm done in class is due to Garg, Konjevod, and Ravi.

The first 2(1-1/k) approximation for multiway cut is due to Dalhaus, Johnson, Papadimitriou, Seymour, and Yannakakis. The first O(log k) approximation for multicut is the region growing algorithm die to Garg, Vazirani and Yannakakis. The randomized technique for multicut was first used by Calinescu, Karloff, and Rabani. In fact, the same idea was present in an earlier paper of the authors which gave a 3/2 approximation for multiway cut. This ratio was improved to 1.35 by Karger, Klein, Stein, Thorrup, and Young .

The first nontrivial algorithm for sparsest cut is by Leighton and Rao (with a gap of 10 years between conference and journal version) who gave a O(log n) approximation. This paper introduced the region growing procedure which was refined in GVY. The relation between sparsest cut and multicut is due to Kahale . The metric embedding connection to algorithm design is made explicit in the paper by Linial, London and Rabinovich.