[Todos CMAT] Curso de Posgrado: Approximation Algorithms.

[Franco Robledo]

Estimados:
     A continuación se dan detalles del curso de Posgrado "Approximation 
Algorithms" a dictarse por el Prof. Maurice Queyranne, University of 
British Columbia.

Fecha de Inicio y Finalización: 3 al 7 de agosto de 2009.
Horario y Salón: de 18 a 21 horas en el Salón Rojo de Posgrado, Facultad 
de Ingeniería. Total de 15 horas de clases teóricas.

Objetivos:
•    Introducción a la Teoría de Algoritmos de Aproximación.
•    Resolución de problemas NP-Hard mediante esta técnica.


Temario:
1) Introduction: Vertex Cover. Combinatorial methods: Metric Steiner 
tree and TSP.
2) LP-based and primal-dual methods: Multicuts, integer multicommodity 
flows, facility location.
3) Local search: k-median, submodular set function maximization. 
Approximation schemes: knapsack.
4) Randomization and derandomization: Max-SAT.  Semidefinite 
programming: Max-cut, graph 3-coloring.
5) Limits to approximability: Clique.  The Unique Games conjecture: 
vertex cover and max-cut revisited.

Inscripciones: bearom en fing.edu.uy (Beatriz Romero, Directora de Posgrados).

Saludos cordiales,
      Franco Robledo Amoza