講義科目： 　　数理情報工学輪講

教員名： 　　　室田一雄　教授

対象： 　　　　4年生

時間： 　　　　夏学期(後半)・月・ 13時〜16時　　2012年6月3日〜7月8日

場所： 　　　　数理ゼミ室301号室

テキスト： 　　W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver:
　　　　　　　　Combinatorial Optimization, John Wiley and Sons, New York, 1998. (ISBN：0-471-55894-X)

概要： 　　　　組合せ最適化分野の名著である．ネットワークフロー，マッチングなどの問題を例にとり最大最小定理，整数性，アルゴリズム，計算量の基礎的な概念と共に，簡単そうに見えてなかなか解けない組合せ最適化の深さを学ぶ．特別な予備知識を必要としない．

本の内容紹介： A complete, highly accessible introduction to one of today's most exciting areas of applied mathematics One of the youngest, most vital areas of applied mathematics, combinatorial optimization integrates techniques from combinatorics, linear programming, and the theory of algorithms. Because of its success in solving difficult problems in areas from telecommunications to VLSI, from product distribution to airline crew scheduling, the field has seen a ground swell of activity over the past decade.

Combinatorial Optimization is an ideal introduction to this mathematical discipline for advanced undergraduates and graduate students of discrete mathematics, computer science, and operations research. Written by a team of recognized experts, the text offers a thorough, highly accessible treatment of both classical concepts and recent results. The topics include:

* Network flow problems * Optimal matching * Integrality of polyhedra * Matroids * NP-completeness

Featuring logical and consistent exposition, clear explanations of basic and advanced concepts, many real-world examples, and helpful, skill-building exercises, Combinatorial Optimization is certain to become the standard text in the field for many years to come.