組合最佳化一   (90年度 上學期)

本課程計畫分上、下兩學期講授，可獨立選修。第一學期的重點在講述線性規劃與對偶原理，強調它們在圖與網絡流上的解釋與應用。在基本的算法中，將特別注重原始對偶法，它把一般線性規劃問題與組合應用緊密聯繫在一起，並且可以給不少組合算法一種統一的觀點。課程討論到的課題包括：單體法及其演算問題、對偶性、原始對偶算法、極大流算法、成本極小流算法、匹配算法等等。

Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Second Edition, Dover, 1998.

期中考（40％）；學期考（60％）。

上課時間：每週二第3節，每週三第3、4節。