UAM


1158070 Optimización en redes
Trimestre 2015 Primavera

Instructores: Dra. Laura Elena Chávez Lomelí, Dr. Marco Antonio Heredia Velasco, Dr. Francisco Javier Zaragoza Martínez.
Inicio y fin del curso: lunes 4 de mayo a viernes 17 de julio de 2015.
Grupos: CPMOPT01 (lunes, miércoles y viernes de 10:00 a 11:30).
Asesorías: En la oficinas H-150, H-287 y H-264.
Salón: E312.
Cupo: 10 alumnos.

Contenido

Se cubrirá el contenido oficial del curso (el cual se detalla abajo). Los temas serán cubiertos por los diferentes instructores.
  1. Gráficas, digráficas y redes [MH].
  2. Problemas de ruta más corta [MH].
  3. Problemas de flujo máximo [MH].
  4. Problemas de flujo de costo mínimo [LC].
  5. Problemas de acoplamientos [LC/FZ].
  6. Problemas de ruteo [FZ].

Evaluación

Habrá cinco evaluaciones. Cada evaluación valdrá 20 puntos. Se requiere obtener

Calendario

El calendario de clases, de entrega de tareas y de evaluaciones que mostramos abajo es tentativo e irá apareciendo paulatinamente.

Bibliografía

  1. Ford Jr. L. R., Fulkerson D. R. (2010). Flows in Networks. Ed. Princeton University Press.
  2. Hernández Ayuso M. C. (2005). Introducción a la teoría de redes. Ed. Sociedad Matemática Mexicana.
  3. Ahuja R. K., Magnanti T. L., Orlin J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Ed. Prentice Hall.
  4. Bertsekas D. P. (1991). Linear Network Optimization: Algorithms and Codes. Ed. The MIT Press.
  5. Vazirani V. V. (2010). Approximation Algorithms. Ed. Springer Berlin Heidelberg.
  6. Hochbaum D. (Editor). (1996). Approximation Algorithms for NP-Hard Problems. Ed. Course Technology.
Problemas de flujo
  1. Bertsekas D.P. (1998). Network Optimization: Continuous and Discrete Models, Athena Scientific.
  2. Cook, W. J., Cunningham, W. H., Pulleyblank, W. R. y Schrijver, A., Combinatorial Optimization, Wiley, New York, 1998.
  3. Rockafellar, R. T., Network Flows and Monotropic Optimization, Wiley, New York, 1984.
Problemas de ruta más corta
  1. Cook W. J, Cunningham W. H., Pulleyblank W. R., Schrijver A. (1998). Combinatorial Optimization [Chapter 2]. Wiley.
  2. Cormen T. H., Leiserson C. E., Rivest R. L. (1999). Introduction to Algorithms [Chapters 23, 25, 26]. McGrawHill.
  3. Korte B., Vygen J. (2006). Combinatorial Optimization: Theory and Algorithms [Chapter 7]. Springer.
  4. Motwani R., Raghavan P. (2006). Randomized Algorithms [Chapter 10]. Cambridge.
  5. Schrijver A. (2003). Combinatorial Optimization [Chapters 6, 7, 8]. Springer.
Problemas de ruteo
  1. Cheriyan J., Ravi R. Lecture Notes on Approximation Algorithms for Network Problems [Chapters 6, 7].
  2. Dror M. (2000). Arc Routing: Theory, Solutions, and Applications. Springer.