## DOCUMENTS AND REPORTS In the following list you will find links to surveys and lecture notes related to approximation. The links were correct in July 1999, but since Internet is always changing some links may be wrong. You could then either try to find the paper by looking at the home page of its author or by searching the Internet for the name of the author and the title of the paper. Sanjeev Arora (1998), The approximability of NP-hard problems, A survey based upon a plenary lecture at ACM STOC'98. Sanjeev Arora (1995), Probabilistic checking of proofs and hardness of approximation problems, Ph.D. thesis. Sanjeev Arora, Carsten Lund (1996), Hardness of approximations. Chapter in the book Approximation Algorithms for NP-hard problems, D. Hochbaum editor, PWS Publishing. A survey that includes proofs of the basic non-approximability applications. László Babai (1994), Transparent proofs and limits to approximation. A survey on proof checking and its applications to obtaining non-approximability results. Mihir Bellare (1996), Proof checking and approximation: towards tight results, a survey with a bibliography. Mihir Bellare, Oded Goldreich, Madhu Sudan (1995-1997), Free bits, PCP and non-approximability - towards tight results, an article describing how to use PCP in non-approximability proofs including a historic survey. Lars Engebretsen (1998), Approximating generalizations of Max Cut, Licentiate thesis in Postscript, PDF, and errata in Postscript and PDF. Michel X. Goemans (1994-1996), lecture notes from MIT course in advanced algorithms: Approximation Algorithms, Linear Programming, Network Flow, TSP algorithms by Karp and Arora. Oded Goldreich (1995-1996), Three texts on probabilistic proof systems: Probabilistic proof systems, a survey, A taxanomy of proof systems, Probabilistic proof systems, lecture notes. Viggo Kann, Alessandro Panconesi (1997), Hardness of approximation, Chapter 2 in Dell'Amico, Maffioli, Martello (editors), Annotated Bibliographies in Combinatorial Optimization, Wiley. Marek Karpinski (1997), Polynomial time approximation schemes for some dense instances of NP-hard optimization problems, a survey. Sanjeev Khanna (1996), A structural view of approximation, Ph.D. thesis. László Lovász (1995), Semidefinite Optimization, Lecture notes (Yale). Rajeev Motwani (1992): lecture notes from Stanford University course in approximation algorithms A.S. Schulz, David Shmoys, David Williamson (1997), Approximation algorithms, Proc. National Academy of Sciences 94. David Shmoys (1995), Computing near-optimal solutions to combinatorial optimization problems, Chapter in the book Combinatorial Optimization, DIMACS series in Discrete Mathematics and Theoretical Computer Science Vol. 20, W. Cook, L. Lovasz, and P. Seymour editors, AMS. A survey of approximation algorithms for combinatorial optimization problems. David Shmoys (1998), Using linear programming in the design and analysis of approximation algorithms: two illustrative problems, Approximation Algorithms for Combinatorial Optimization, LNCS 1444 (K. Jansen and J. Rolim, eds.), Springer, Berlin. Madhu Sudan (1995), On the role of algebra in the efficient verification of proofs, A short article about the error-correcting codes viewpoint which underlies the constructions of efficiently checkable proofs. Stefan Thienel (1995), ABACUS - A Branch-And-CUt System, Ph.D. Thesis, Universität zu Köln. Luca Trevisan (1997), Reductions and (non)-approximability, Ph.D. thesis (link). Vijay Vazirani (1997-1999), Approximation algorithms, draft to a monograph. David Williamson (1998), Lecture Notes on Approximation Algorithms at Columbia (spring 1998), at Cornell (fall 1998). Margaret H. Wright (1991), The interior-point revolution in constrained optimization.