[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