[Todos CMAT] Curso de Posgrado: Approximation Algorithms.

Franco Robledo frobledo en fing.edu.uy
Mie Jul 15 12:45:00 UYT 2009


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, FING).

Saludos cordiales,
Franco Robledo Amoza


Más información sobre la lista de distribución Todos