藤重 悟 （ふじしげ さとる）,　教授　　　　　    

 専門分野:　数理工学,　数理計画,　離散最適化,　離散アルゴリズム 

　 略歴

---

＜学生諸君へのメッセージ＞

確率的制御理論の研究をして，博士の学位を取得しましたが， 東京大学の伊理正夫教授(当時)のもとで働く 機会を得て，伊理先生のご指導を受け離散最適化の研究にのめり込み，現在に至って います．素晴らしい先生に巡り会えた幸運に感謝しています．私は，現在，学生を 指導する立場になって，私との巡り会いを幸運に思ってくれる学生を一人でも多く 出したいと努力しています．

「離散最適化」と「アルゴリズム」，広くは，数理工学，数理計画，システム科学 に興味を持つ学生は，遠慮なく私のオフィスを訪問してください．

共立出版社から出版された拙著（ 「グラフ・ネットワーク・組合せ論」 ）も参考にしてください．

---

研究分野

• 数理工学,　離散システム,　組合せ最適化,　離散アルゴリズム

---

研究テーマ

• グラフ・ネットワーク・マトロイドなどの離散構造を有するシステムの最適化
• 劣モジュラ構造と組合せ最適化モデル
• 最適化アルゴリズム (ネットワーク最適設計，最適施設配置，スケジューリング，. . . )
• 最適化と凸多面体(効率的アルゴリズムと多面体的組合せ論)
• LP-Newton 法 と 線形計画

---

最近の主な研究論文

• S. Fujishige, T. Hayashi, and K. Nagano: "Minimizing continuous extensions of discrete convex functions with linear inequality constraints " SIAM Journal on Optimization, Vol. 20 (2009), pp. 856--867.

• S. Fujishige and K. Nagano: "A structure theory for the parametric submodular intersection problem " Mathematics of Operations Research, Vol. 34 (2009), pp. 513--521.

• S. Fujishige: "A note on disjoint arborescences " Combinatorica (to appear)."

• S. T. McCormick and S. Fujishige: "Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization " Mathematical Programming, Vol. 122 (2009), pp. 87--120.

• S. Fujishige, T. Hayashi, K. Yamashita, and U. Zimmermann: "Zonotopes and the LP-Newton method " Optimization and Engineering, Vol. 10 (2009), pp. 193--205.

• M. Sakashita, K. Makino, H. Nagamochi, and S. Fujishige: "Minimum transversals in posi-modular systems " SIAM Journal on Discrete Mathematics, Vol. 23 (2009), pp. 858--871.

• U. Faigle and S. Fujishige: "A general model for matroids and the greedy algorithm" Mathematical Programming, Ser. A, Vol. 119 (2009), pp. 353--369.

• M. Sakashita, K. Makino, and S. Fujishige: "Minimizing a monotone concave function with laminar covering constraints" Discrete Applied Mathematics, Vol. 156 (2008), pp. 204--219.

• M. Sakashita, K. Makino, and S. Fujishige: "Minimum cost source location problems with flow requirements" Algorithmica, Vol. 50 (2008), pp. 555--583.

• S. Fujishige, G. A. Koshevoy, and Y. Sano: "Matroids on convex geometries" Discrete Mathematics, Vol. 307 (2007), pp. 1936--1950.

• S. Fujishige and A. Tamura: "A two-sided discrete-concave market with possibly bounded side payments: an approach by discrete convex analysis" Mathematics of Operations Research, Vol. 32 (2007), pp. 136--155.

• S. Iwata, L. Fleischer, and S. Fujishige: "A combinatorial strongly polynomial algorithm for minimizing submodular functions" Journal of ACM, Vol. 48 (2001), pp. 761-777 [2003 Fulkerson Prize-winning paper]

• S. Fujishige: "A maximum flow algorithm using MA ordering" Operations Research Letters, Vol. 31 (2003), pp. 176--178.

  Also see: S. Fujishige and S. Isotani: "New maximum flow algorithms by MA orderings and scaling " Journal of the Operations Research Society of Japan, Vol. 46 (2003), pp. 243-250; and Y. Matsuoka and S. Fujishige: "Practical efficiency of maximum flow algorithms using MA orderings and preflows " Journal of the Operations Research Society of Japan, Vol. 48 (2005), pp. 297-307.

---

A code in C for submodular function minimization is available upon request.

---

過去の主要な研究成果　 リスト

---

主要著書

• 高橋・藤重：「離散数学」（岩波情報科学講座、 第１７巻、 岩波書店、 １９８１年）
• 伊理・藤重・大山：「グラフ・ネットワーク・マトロイド」（講座：数理計画、 第７巻、 産業図書、 １９８６年）（２００５年１２月復刊(初版の誤植やミスを訂正し、参考図書を追加)、現在入手可能です！）
• 伊理・藤重：「応用代数」（電子情報通信学会大学シリーズA-1、コロナ社、 １９８８年）
• S. Fujishige: ``Submodular Functions and Optimization'' （North-Holland, １９９１年） (第２版、Elsevier, ２００５年７月)
• 藤重：「離散数学」（岩波応用数学講座、基礎１２、 岩波書店、 １９９３年）
• 藤重：「グラフ・ネットワーク・組合せ論」（工系数学講座、１８、 共立 出版、 ２００２） コメント

---

その他

• 数学入門公開講座（平成１７年度担当）「劣モジュラ構造と離散凸性」 テキスト

• 「離散凸関数のお話」日本OR学会北海道支部講演会(2007年12月4日) 講演資料

---

オフィス ： 総合研究２号館４階 473室　(本館改修中）

E-mail : fujishig (at) kurims.kyoto-u.ac.jp

---

数理解析研究所ホームページ

数理計画研究部会

---