TOKUTEI: algorithm A01han kaigi 99/06/24
平成11年度第1回A01班会議 議事録
<<研究会>>
日時:平成11年6月24日(木) 10:00-17:00
場所:東京大学山上会館002号室
出席者リスト(順不同;31名+α):
室田一雄(班長), 茨木俊秀, 田村明久, 柳浦睦憲, 藤沢克樹, 降旗大介(京都
大学),石井博昭, 藤重悟, 岩田覚, 斉藤誠慈, 浜邦彦 (大阪大学),久保幹雄
(東京商船大),伊藤大雄(豊橋技科大),浅野孝夫, 今井桂子, 亀田貴之, 堂免俊
介(中央大学),塩出省吾, 毛利進太郎(神戸学院大),塩浦昭義(上智大), 伊藤美
保, 井上雅史, 工藤崇徳(東京理科大),土村展之(ログオプト),今井浩, 定兼邦
彦, 竹内史比古, 徳永裕己, 石関隆幸, 長井歩, 浅野泰仁(東京大学)
A01班班会議での研究会部分を以下のように行なった.なお,5件の発表のうち
の次の3件
については,発表に用いた資料へのリンクを張っている.資料を閲覧
以外の目的で使う場合は,各発表者に連絡をとること.
プログラム:
10:00-11:00 浅野孝夫 (中央大学 情報工学)
『グラフ・ネットワークアルゴリズムのデータベース化』
グラフ・ネットワークアルゴリズムの近年の発展を概観し,それを踏まえ
てそれらアルゴリズムのデータベース化について述べられた.このデータ
ベース化を推進するA02班の5月26日班会議の成果についても触れられた.
11:00-12:00 今井浩 (東京大学 情報科学)
『マトロイド不変多項式の基礎』
マトロイドの不変多項式にTutte多項式について,WelshのLecture Notesを
軸にその理論的背景が説明された.また,研究グループの成果についても
述べられた.
13:30-14:30 毛利 進太郎 (神戸学院大学), 石井 博昭 (大阪大学工学研究科)
『多目的スケジュ−リング問題の近似解法』スケジュ−リング問題は単一
の目的関数の場合でも大規模な問題は計算時間の上から解くことが困難で
あり,一方で現実のスケジュ−リングでは多目的の場合が多く、この点で
シンプルで精度のよい近似解法が望まれている.この近似解法に関する研
究グループのこれまでの成果について述べられた.
14:30-15:30 伊藤大雄 (豊橋技術科学大学 情報工学系)
『二次元ハムサンドイッチ定理の一般化とその周辺』
「平面上に赤点$pn$個、白点$pm$個が配置されている時(但し任意の3点
は同一直線上に無いとする)、互いに重ならない$p$個の凸領域が存在し、
各領域は丁度赤点$n$個、白点$m$個を含む様にできる」という2次元ハムサ
ンドイッチ定理の一般化の証明について発表された.
16:00-17:00 藤沢克樹 (京都大学 建築情報システム学)
『SDPA(半正定値計画問題に対するソフトウェア)と大規模広域計算システム Ninf』
発表では、SDPA の設計思想や実装方法に触れると共に、SDPA や LPソフト
ウェアを用いた新しい大域的最適化手法の広域計算システム Ninf への適
用、Ninf 専用の SDPA の開発、及びインターネットを通じたこれらのシス
テムの利用方法について述べられた。
<<班会議>>
日時: 平成11年6月24日(木)5時30分〜6時30分
場所: 東京大学 理学7号館 202会議室
参加者(敬称略): 伊藤大雄, 茨木俊秀, 今井浩, 久保幹雄, 斎藤誠慈, 定兼邦彦,
土村展之, 藤澤克樹, 藤重悟, 室田一雄, 柳浦睦憲
1. 各研究代表者から提出予定のプログラムの対象 --- "[]"は検討中
・茨木: 充足最大化問題, 一般化割当問題, 制約充足問題,
資源制約つきスケジューリング問題, [集合被覆問題]
・室田: 劣モジュラ流 / マトロイドインタセクション, 行列分解(CCF),
M凸関数最小化
・藤重: 劣モジュラ関数最小化(2種類), 多品種流問題
・石井: 多目的スケジューリング問題の近似アルゴリズム,
ネットワーク信頼度の近似計算
・増山: 複数記事要約, AGVシステムのシミュレータと運行制御アルゴリズム,
関連記事検索
・今井: 量子コンピュータ, Tutte多項式, 文字列の suffix sorting,
文章キーワードの検索, 最短路(A02班でも作成?), [オセロ, BDD]
・久保: グラフ分割, 最大クリーク(以上2つはX-WINDOWS上でビジュアルなデモ可能),
二次割当, 多次元ナップサック, 集合被覆問題, 巡回セールスマン問題,
K-メジアン, [グラフ彩色問題, ジョブショップ問題, 整数計画問題,
配送計画問題, ネットワークデザイン]
・土村: データベース受入れ & デモ画面作成
- スケジューリング問題(野々部@京大)
- 量子計算のシミュレーション(徳永@東大)
→ 内容の手本とする(デモやドキュメントなど).
10月27から29日の全体会議において発表する.
2. 次回A01班班会議:
日程: 12月22日(水)
場所: 大阪? (藤重先生と石井先生で担当)
発表者: 次回10月の全体会議の際に決定.
梅谷 俊治
<最終更新作成日時 1999年7月7日 >