MAC0325 + MAC5781 Otimização Combinatória
Catálogo da Biblioteca do IME/USP
Os comentários nesta página forma feitos por Paulo Feofiloff em http://www.ime.usp.br/~pf/mac5781-2002/bib.html.
Nossa referência básica é conhecida como "o AMO":
R.K. Ahuja, Th. L. Magnanti, J.B. Orlin,
Network Flows: Theory, Algorithms, and Applications,
Prentice Hall, 1993.
AMO é mais um manual que um livro-texto. Tem uma grande quantidade de material, bons exercícios e muitas aplicações interessantes. Também tem alguns defeitos. A tipografia é de má qualidade e tem muitos erros. A notação é descuidada e por vezes inconsistente. Os algoritmos são descritos de maneira imprecisa, e não raro contêm erros tipográficos. Os enunciados dos teoremas freqüentemente omitem hipóteses importantes. As condições de aplicabilidade dos algoritmos nem sempre estão claras. Vários capítulos começam por impor restrições (assumptions) sobre as redes em estudo, mas no decorrer do capítulo nem sempre fica claro onde e por que as restrições são necessárias.
O professor Paulo Feofiloff
preparou um texto excelente sobre Fluxos em Redes baseado no AMO. Este texto
está disponível na sua página de
MAC0325+MAC5781 (veja
as notas de aula).
Nosso livro alternativo, conhecido como "o CCPS", foi muito bem escrito por quatro dos maiores especialistas da área:
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver,
Combinatorial Optimization,
John Wiley, 1998.
Um livro enciclopédico sobre o assunto é
A. Schrijver,
Combinatorial Optimization: Polyhedra and Efficiency,
Springer, 2003.
Além desses livros, é preciso citar o CLRS (a primeira edição do livro era conhecida como "o CLR"), que contém uma parte do material da disciplina:
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
Introduction to Algorithms, 2nd. edition,
MIT Press e McGraw-Hill, 2001.