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

 A. Kononov

Combinatorial Optomization
 Presentation

Master Course. Second year.
 

Lecture 1 Introduction CO1new.ppt
Lecture 2 Graphs CO2new.ppt
Lecture 3
Connectivity
 CO3new.ppt
Lecture 4 Spanning tree CO4new.ppt
Lecture 5 Shortest Paths CO5new.ppt
Lecture 6 Network Flows CO6new.ppt
Lecture 7 Network Flows CO7new.ppt
Lecture 8 NP-Completness CO8new.ppt
Lecture 9

Cook Theorem and NP-complete problems

 		 CO9new.ppt
Lecture 10 NP-Hard Problems CO10new.ppt
Lecture 11

 

 		  
Topics for Exam    
     

 

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  

Редакция 22.12.2015