[EstudiantesMatemática] Fwd: Curso de Posgrado: Approximation Algorithms.

[Elisa Rocha]

---------- Forwarded message ----------
From: Franco Robledo <frobledo en fing.edu.uy>
Date: 2009/7/27
Subject: Curso de Posgrado: Approximation Algorithms.
To: todosimerl <todos_imerl en fing.edu.uy>, todos en cmat.edu.uy,
todos en fcien.edu.uy, todos_imfia en fing.edu.uy, invop en fing.edu.uy,
sermon en fing.edu.uy, artes en fing.edu.uy


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
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://www.cmat.edu.uy/pipermail/listaestudiantes/attachments/20090727/aa516091/attachment.htm>