ChE 469: Approximation Algorithms

---

Instructor: Nick Sahinidis (nikos@uiuc.edu)

---

Course Objective: To offer an introduction to approximation algorithms for hard combinatorial optimization problems. Topics covered will include polynomial approximation schemes using: dual, primal-dual, greedy algorithms, semidefinite programming relaxations, randomized rounding.

---

Credit: 0.25 unit. Students will be required to present material from the references below.

---

Prerequisites: Linear programming, integer programming/combinatorial optimization, computational complexity.

---

Schedule of Lectures (Dates and abstracts of lectures)

---

References:

• S. Arora, Selected publications on complexity and approximation, Princeton University.
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi, Complexity and approximation: Combinatorial optimization problems and their approximability properties, Springer, Berlin, 1999.
• P. Crescenzi and V. Kann (eds.), A list of NP-complete optimization problems and their approximability, KTH, Royal Institute of Technology, Stockholm, Sweden.
• D. Hochbaum (ed.), Randomization, approximation, and combinatorial optimization: algorithms and techniques, Springer, Berlin, 1999.
• J. Cheriyan and R. Ravi, Approximation Algorithms for Network Problems, September 1998.
• M. Goemans, Approximation Algorithms, MIT, Fall 1994.
• R. Motwani, Lecture notes on Approximation Algorithms--Volume I.
• R. Motwani and P. Raghavan, Randomized algorithms, Cambridge University Press, Cambridge, 1995.
• P. Pardalos (ed.), Approximation and complexity in numerical optimization, Kluwer Academic Publishers, Boston, 2000.
• David P. Williamson, Lecture notes on approximation algorithms, see Approximation algorithms course, MIT, Spring 2000.
• V. Vazirani, Approximation Algorithms (preliminary draft).

---

Web pages of similar courses:

• David P. Williamson, Approximation algorithms course, MIT, Spring 2000.
• Joseph Cheriyan, Approximation Algorithms, Fields Institute, Fall 1999.
• Madhu Sudan, Approximability of Optimization Problems, MIT, Fall 1999.
• Uri Zwick, Approximation Algorithms, Tel Aviv University, Fall 1999.
• David Shmoys and Eva Tardos, Topics in Mathematical Programming: Approximation Algorithms, Cornell, Spring 1999.
• Lenore Cowen, Approximation Algorithms, Johns Hopkins, Fall 1998.
• Yuval Rabani, Approximation Algorithms, Technion, Fall 1995.

---

To Sigma Optimization Teaching Activities