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.
|