Combinatorial Optimization

Instructor : Kourosh Eshghi

E-mail : eshghi@ sharif.edu        

 Home Page :  http://sharif.edu/~eshghi/                

Tel:  66165712          

 

Major Topics:    

Section 1: (Analysis of Algorithms )

Section 2: (Search Techniques for Combinatorial Optimization Problems)

 

1.      What is an Algorithm?

2.      Asymptotic Analysis

3.      Analysis of Algorithms

4.      Finite State Machine

5.      Turing Machine

6.      The Theory of  NP-completeness

7.      Basic NP-complete Problems

 

1. Search Techniques

2.Genetic Algorithms

3. Ant Colony Optimization Algorithm

4. Tabu Search Technique

5. Simulated Annealing

 

Prescribed  Texts:

Section 1:

1.  An Introduction to Algorithm, Thomas H. Cormen  et al., 2000.

2. Computers and Intractability, Guide to NP-completeness, Garey and Johnson,    1979.

Section 2:

1. Intelligent Optimization Techniques, Pham and Karaboga, 2000.

2. Combinatorial Optimization: Algorithms and Complexity, Papadimitriou and Steiglitz, Prentice- Hall , 1998.

 

 Interesting Links

 A list of NP-complete problems