PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2007.2
Horário: 4as-feiras de 16 às 19 horas
OTIMIZAÇÃO COMBINATÓRIA (INF 2912)
www.inf.puc-rio.br/ ~ poggi/oc72.html
Descrição:
-
Este curso aborda técnicas para o desenvolvimento de algoritmos para um amplo conjunto de problemas de otimização combinatória.
CONTEÚDO
-
Introdução: Programação Linear, Dualidade, Algoritmo Simplex, Complementaridade de Folgas, Algoritmo Primal Dual.
-
Algoritmo Primal-Dual em Otimização Combinatória: Caminho-Mais-Curto, Fluxo Máximo, Fluxo a Custo Mínimo, Fluxos com Ganhos, Problema de Transportes, Problema de Alocação Linear, Problema de Emparelhamento, Grafos Bi-partidos e Não bi-partidos.
-
Problemas em Grafos: Árvores geradoras mínimas, caminho mais curto, emparelhamento máximo não-ponderado e ponderado, assignment, cortes mínimo e máximo, coloração de vértices e arestas, problema de Steiner, caixeiro viajante e roteamentos.
-
Métodos básicos: algoritmos gulosos e matróides, programação dinâmica,
algoritmos para programação linear e inteira, decomposição, relaxação Lagrangeana, branch-and-bound.
-
Aplicação a problemas NP-difíceis: algoritmos aproximativos e aproximados,
limites inferiores e superiores, heurísticas duais e primais.
AVALIAÇÃO
Listas, seminários e trabalhos de implementação.
BIBLIOGRAFIA
Livro Texto:
-
C. Papadimitriou e K. Steiglitz,
Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982.
Bibiligrafia Adicional
-
R.K. Ahuja, T.L. Magnanti e J.B.Orlin,
Network Flows, Prentice Hall, 1993.
-
G.L. Nemhauser e J. L.A. Wolsey, Integer and Combinatorial Optimization,
John Wiley & Sons, 1988.
- W.J. Cook, W.H. Cunningham, W.R. Pulleyblank e A. Schrijver,Combinatorial Optimization, John Wiley and Sons, New York, 1998.
-
J. L.A. Wolsey, Integer Programming,
Wiley Interscience, 1998.
-
N. Christofides,
Graph Theory: An Algorithmic Approach, Academic Press, 1975.
-
E. Horowitz e S. Sahni, Fundamentals of Computer Algorithms,
Computer Science Press, 1978-89.
-
M. Garey e D. S. Johnson,Computers and
Intractability: A Guide to the Theory of NP-Completeness
W.H.Freeman and Company, 1979.
-
U. Manber, Algorithms: A Creative Approach,
Addison-Wesley, 1989.
-
R.E. Tarjan, Data Structures and Network Algorithms,
SIAM, 1983.
-
P.A. Jensen e W. Barnes, Network Flow Programming, Wiley, 1980.
-
M. Gondran e M. Minoux, Graphs and Algorithms, Wiley-Interscience, 1984.
- T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction
to Algorithms, McGraw-Hill, New York, 1990.
-
G. Brassard e P. Bratley, Algorithmics: Theory and Practice, Prentice-Hall, 1988.
This document was translated from LATEX by HEVEA.