Novosibirsk State University
Theoretical Cybernetic Department
 Thin_Red_and_BlueA205.gif (1558 bytes)

 A. Kononov

Approximation Algorithms
 Presentation

Master Course. First year.
 

Lecture 1. Introduction AppEngLect1-2017.pdf
Lecture 2. Combinatorial algorithms. Set cover AppEngLect2-2017.pdf
Lecture 3.
Combinatorial algorithms. Metric problems
AppEngLect3-2017.pdf
Lecture 4. Combinatorial algorithms. Local search AppEngLect4-2017.pdf
Lecture 5. Approximation schemes. Scheduling problems AppEngLect5-2017.pdf
Lecture 6. Approximation schemes. Bin packing problems AppEngLect6-2017.pdf
Lecture 7. Approximation schemes. Open shop AppEngLect7-2017.pdf
Lecture 8. Linear programming. Scheduling problems AppEngLect8-2017.pdf
Lecture 9. Linear programming. Set cover AppEngLect9-2017.pdf
Lecture 10.

Randomized algorithms. MAX-SAT

 		 AppEngLect10-2017.pdf
Lecture 11.

Linear programming. Separation oracle

 		 AppEngLect11-2017.pdf
     
     

 

Textbooks

1.  М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. с. 154–191. (djvu-file 10 Mb)

2.  B. Korte, J. Vygen. Combimatorial Optimization. Theory and Algorithms. Berlin: Springer-Verlag, 2002. (pdf-file 22 Mb)

3.  V. Vazirani, Approximation Algorithms, Berlin: Springer-Verlag, 2001. (pdf-file 14 Mb)

4. Х. Пападимитриу, К. Стайглиц.   Комбинаторная  оптимизация. Алгоритмы и сложность. М.: Мир, 1985. (djvu-file 4,5 Mb)

5. P. Schuurman, G. Woeginger.  Approximation Schemes – A Tutorial, chapter of the book “Lecture on Scheduling” (pdf-file 0,5 Mb)

6. D.Hochbaum (Ed.) Approximation Algorithms for NP-hard problems. PWS Publishing Company, 1997.

 

Professor Alexandr Kononov
e-mail:  alvenko@math.nsc.ru  

Редакция 26.04.2017