Approximation Algorithms

Books and lecture notes

	Hochbaum, D.S. (1996). Approximation algorithms for NP-hard problems. (Boston: PWS publishing co.).
	David Williamson, Lecture Notes on Approximation Algorithms, Fall 1998. IBM Research Report RC 21409, February 1999.
	Cheriyan and Ram Ravi, Lecture Notes on Approximation Algorithms for Network Problems.
	P.Crescenzi, and V.Kann. A compendium of NP optimization problems.
	Vijay Vazirani, Monograph on Approximation Algorithms.

Online papers

For Bin Packing:

An interesting website.
Approximation Algorithms for Bin Packing: A Survey, E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson, Approximation Algorithms for NP-Hard Problems, D. Hochbaum (editor), PWS Publishing, Boston (1997), 46-93. A survey of worst- and average-case results for the classical one-dimensional bin packing problem.

For shortest common super string:

Linear Approximation of Shortest Superstrings , by Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis in STOC'91 and Journal of ACM, 41:4 (1994), 630-647.
T. Jiang and M. Li. On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput., 24:1122--1139, 1995.

For closest string:

M. Li, B. Ma and L. Wang, On the Closest String and Substing Problems , accepted by Journal of the ACM , Jan. 2002.
K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang, Distinguishing string search problems, to appear in Information and Computation, accepted Jan. 2000. (Also appeared in SODA'99.)

For Tree Alignment

Lusheng Wang, Tao Jiang, Dan Gusfield, A More Efficient Approximation Scheme for Tree Alignment. SIAM Journal on Computing, Volume 30, Number 1:283-299.
Lusheng Wang, Tao Jiang, Eugene L. Lawler: Approximation Algorithms for Tree Alignment with a Given Phylogeny. Algorithmica 16(3): 302-315 (1996)
Lusheng Wang, Dan Gusfield: Improved Approximation Algorithms for Tree Alignment. J. Algorithms 25(2): 255-273 (1997)

For Inapproximability:

Papadimitriou, C. H., and Yannakakis, M. (1991), ``Optimization, approximation, and complexity classes'', J. Comput. System Sci. 43, 425-440.
A chapter on the book "Approximation Algorithms for NP hard optimization problems".

For phylogeny tree reconstruction (additive tree fitting):

M.Farach, S. Kannan and T. Warnow, A robust model for finding optimal evolutionary trees, Algorithmica, vol. 13, pp. 155-179, 1995.

Similar courses in other Universities

	http://www.brics.dk/Activities/96/Approximation/
	Approximatin Algorithms, Tel AvivUniversity Fall 1999
	Approximation Algorithms, Fields Institute, Fall 99 (Lecturer: Joseph Cheriyan)
	Approximability of Optimization Problems, MIT, Fall 99 (Lecturer: Madhu Sudan)
	Topics in Mathematical Programming: Approximation Algorithms, Cornell, Spring 99 (Lecturer: David Shmoys)
	Approximation Algorithms, Johns Hopkins, Fall 98 (Lecturer: Lenore Cowen)
	Approximation Algorithms, Technion, Fall 95 (Lecturer: Yuval Rabani)