Operations Research (UGA)

Skills

•     Theoretical background
  •         know that a computational model called the Turing Machine exists, and that it is the reference model
•     Vocabulary
  •         Identify a decision problem and an optimisation problem
  •         be able to write down the decision problem associated with an optimisation problem and vice versa
  •         know the definitions of the classes P and NP and their inclusion relations, and the associated conjecture
•     NP-completeness
  •         know how to prove that a problem is in NP
  •         know how to prove that a problem is NP-hard
•     SAT and 3-SAT
  •         Know the definitions of SAT and 3-SAT problems
  •         Know that they are NP-complete
•     Hamiltonian circuit, Hamiltonian cycle and TSP  
  •         Know the definitions of Hamiltonian circuit, Hamiltonian cycle and TSP problems
  •         Know that they are NP-complete and be able to redo the proof for TSP
•     Clique, Coloration, 3-coloration
  •         Know the definitions of these problems
  •         Know that they are NP-complete and be able to redo the proof for Clique
•     co-NP class
  •         Know the definition of the complexity class
  •         Know how to prove that a problem is in co-NP
  •         Know an example of a problem in co-NP

Ressources

Vidéos

Readings

• Computers and Intractability: A Guide to the Theory of NP-Completeness, M.R. Garey, D.S. Johnson 
        (the reference book)
  
• Computational complexity, C.H. Papadimitriou
  
• A guide to algorithm design, A. Benoit, Y. Robert, F. Vivien
• The Algorithm design manual, S. S. Skiena
        chap 9: Intractable Problems and Approximation Algorithms
• Algorithms (Chap 8)  by Dasgupta, Papadimitriou and Vazirani
  

Web sites