A01班 班会議

===============================================================
  科研費特定領域研究「新しいパラダイムとしてのアルゴリズム工学」
       A01班(離散最適化アルゴリズム)　 班会議のお知らせ
===============================================================

この班会議の目的は, 共同研究への発展を目指して, 相互の研究活動を理解する
ことにあります．
講演者一人の持ち時間は６０分とし, ４０分間講演, ２０分間質疑応答討論という
形式で，実質的な研究交流を狙います．A01班以外の方の参加も歓迎します．

日時：平成11年6月24日(木) 10:00-17:00
場所：東京大学山上会館002号室
      （東京大学本郷キャンパス三四郎池横；
        最寄り駅：営団地下鉄南北線「東大前」駅
                  営団地下鉄千代田線「根津」駅
                  営団地下鉄丸の内線「本郷３丁目」各１０分
                  ＪＲ「上野」駅から徒歩２０分
　　◎東京大学のホームページ： http://www.u-tokyo.ac.jp/index-j.html
　　　の最後のあたりに地図をクリックするところがあります．

講演者と講演タイトル：

10:00-11:00 浅野孝夫 (中央大学 情報工学)
   『グラフ・ネットワークアルゴリズムのデータベース化』

   グラフ・ネットワークアルゴリズムの近年の発展を概観し，それを踏まえてそ
   れらアルゴリズムのデータベース化について述べる．このデータベース化を推
   進するA02班の5月26日班会議の成果についても触れる．

11:00-12:00 今井浩 (東京大学 情報科学)
   『マトロイド不変多項式の基礎』

   マトロイドの不変多項式にTutte多項式がある．これはグラフの場合，彩色多
   項式やフロー多項式，さらにはグラフの木・全域部分グラフの数，ネットワー
   ク信頼度多項式を特別な場合として含み，統計物理でのIsingモデルや浸透な
   どさまざまな関数とも関連し，結び目のJones多項式とも関係する．また，幾
   何の観点からも，超平面アレンジメントのセル数，そのグラフの場合の
   acyclic orientationsの数などを与えることもわかっている．
  この一連の問題を計算の観点から解説したものに，WelshのLecture Notesがあ
   る．本発表ではそれの解説を主に行なうことを目標とする．そして，著者らの
   グループで開発している2分決定グラフを計算過程として用いる解法について
   述べ，上のような幅広い展開での各局面への検討状況について述べる．

13:30-14:30 毛利進太郎 (神戸学院大学), 石井博昭 (大阪大学工学研究科)

   『多目的スケジュ−リング問題の近似解法』

   スケジュ−リング問題は単一の目的関数の場合でも大規模な問題は計算時間の
   上から解くことが困難である．しかし現実のスケジュ−リングでは多目的の場
   合が多く、この点でシンプルで精度のよい近似解法が望まれる．このため我々
   は新しい近似解法の基礎的研究に着手しており、この辺りを中心に近似解法を
   紹介する．

14:30-15:30 伊藤大雄 (豊橋技術科学大学　情報工学系)

   『二次元ハムサンドイッチ定理の一般化とその周辺』

   「平面上に赤点$pn$個、白点$pm$個が配置されている時（但し任意の３点は同
   一直線上に無いとする）、互いに重ならない$p$個の凸領域が存在し、各領域
   は丁度赤点$n$個、白点$m$個を含む様にできる」という金子、加納の予想は
   $p=2$とすると有名なハムサンドイッチ定理（但し２次元版）であり、それを
   一般化した重要な予想であった。本予想に対し昨年、伊藤らによって証明が提
   示された。本発表ではこの証明の概要を紹介すると同時に昨年から今年にかけ
   て、発表された類似の問題に関する結果をいくつか紹介する。

16:00-17:00 藤沢克樹 (京都大学 建築情報システム学)

   『SDPA(半正定値計画問題に対するソフトウェア)と大規模広域計算システム Ninf』

   工学系などの複雑な実用問題に対する非凸最適化(大域的最適化)において、大
   規模な問題を解くためには理論面での進歩と共に、高速なソフトウェア、及び
   それらを実行するための大規模な計算インフラが不可欠である。そこで本発表
   では、SDPA の設計思想や実装方法に触れると共に、SDPA や LPソフトウェア
   を用いた新しい大域的最適化手法の広域計算システム Ninf への適用、Ninf 
   専用の SDPA の開発、及びインターネットを通じたこれらのシステムの利用方
   法について述べる。

◎「新しいパラダイムとしてのアルゴリズム工学」のホームページ:
    http://www.kuamp.kyoto-u.ac.jp/labs/or/tokutei98/

会場連絡先：
   〒113-XXXX 東京都XXX
   東京大学YYYZZZZ
   今井浩
   E-mail: imai＠hoge.u-tokyo.ac.jp
   Tel: 03-XXXX-XXXX, Fax: 03-YYYY-YYYY