Instructor: M. C. Pinar

Room: 321B

Office Hours: Open door policy

Textbook and Reference Material:

- Integer Programming by L. Wolsey, 1998, Wiley & Sons.
- An introduction to complexity, polyhedral theory and combinatorial optimization by G. Dahl
- A survey on primal-dual approximation algorithms by M. Goemans and D. Williamson.
- Slides of lecture notes on primal-dual approximation algorithms by D. Williamson.
- A more recent survey on primal-dual approximation algorithms by D. Williamson.
- Slides of more recent lecture notes on primal-dual approximation algorithms by D. Williamson.
- Slides of introductory lecture notes on primal-dual approximation algorithms by E. Bauer and M. Zinkevitch.
- Lecture notes on approximation algorithms by Vazirani.

The students are expected to acquire basic skills in using the AMPL modeling language. For general information see AMPL's site. You can find a library of ampl solution models here.

We will also be using the GAMS modeling language. The students will be asked to familiarize themselves with GAMS through homework exercises. Feel free to visit the GAMS homepage and browse the large collection of models.

The syllabus is available here.

Grading

Homeworks: 60 %

- Hw1: Due
- Hw2: Due
- Hw3: Due
- Hw4: Due
Term Paper: 0 %

Final: 40 % Take home

- due date: June 4, 2001
- The two toy problems for you to check your algorithms
- I. 5 clients, 4 potential facilities, p=2
- 2 5 9 7
- d_ij = 3 7 6 1
- 5 8 3 7
- 4 3 9 1
- 6 1 3 7
- II. 5 clients, 4 potential facilities, p=2
- 2 3 5 4
- d_ij = 3 7 5 1
- 6 5 4 1
- 6 7 3 6
- 1 6 8 4
Participation: 0 %