1. 総括班の活動
総括班では, これまでに予備会議を2回と班会議を1回開催した. 3月に今年度最後の班会議をもう一度行う予定である. これらの日時などは以下の通りである.
2. 全体の活動
全体的な活動としては, これまでに1回の全体会議を行っており, また, 今年度中に全体会議をもう1度と国際シンポジウムを共催する予定である. 第1回の全体会議では, 全ての研究代表者が, 現在の研究テーマと 本特定領域研究で計画している研究について講演を行った. 参加人数は60名程度であった. 第2回の全体会議では, 各班でこれまでに得られている暫定的な研究成果を 班ごとに総括して発表が行われる予定である. また, 「パラダイムとしてのアルゴリズム工学」と いう概念を明確にし, 今後2年間の研究の方向を定めることを目標に, パネルディスカッションを予定している. 国際シンポジウム「離散数学とその応用に関する日洪シンポジウム」 では, 3件の招待講演と, 39件の一般講演を予定している. これらの日程は以下の通りである.
3. 電子情報通信学会の特集号
新しいパラダイムとしての「アルゴリズム工学」という我々の主張を 広め, また「アルゴリズム工学」の現状を説明するために, 電子情報通信 学会の英文論文誌に特集号を組むため, 以下の要領で企画が進行中である. 当領域研究に参加する研究代表者全員が著者としてそれぞれの専門分野における アルゴリズム工学の最近の知見をサーベイするとともに, 適切な著者がいない重要な分野については 外部からの招待論文を企画することで, すべてのアルゴリズム工学研究者にとって なくてはならない論文集とすることを目指している.
4. 平成10年度A01班活動/成果報告
平成10年度において,A01班は全体会議の際に各々班会議も同時に開催し,ま た班独自に12月に研究会形式の研究会を開催した.本年度が研究初年度にあた ることに鑑み,班として「アルゴリズム工学」共同研究推進を可能となるよう な運営を行なっている.以下,個別の会についてまとめる.
4.1. 平成10年度第1回班会議
4.2. 平成10年度第1回研究会
A01班平成10年度最終の班会議を全体会議の際に合わせて下記日程で予定している.
5.平成10年度A02班活動/成果報告
平成10年度A02班の活動報告をお知らせいたします.
A02班は6名の研究代表者(浅野孝夫(中央大学理工学部),戸田誠之助(日本大文学
理学部),周暁(東北大学情報科学研究科),永持仁(京都大学工学研究科),平田
富夫(名古屋大学工学研究科),渡辺敏正(広島大学工学部))
およびその研究分担者より構成されています.
主な研究対象は離散最適化問題の中でも特殊な構造をもち
かつ基礎的であるグラフ・ネットワーク問題とSAT(充足可能性問題)であります.
平成10年度はアルゴリズム工学の立場から以下のように研究集会を開催し, グルー
プ内の研究者および他のグループとの情報交換を行ない,共通の目的意識を形成しま
した.
5.平成10年度A03班活動/成果報告
6.平成10年度A04班活動/成果報告
特定領域研究(B)「新しいパラダイムとしてのアルゴリズム工学」
A04班 ( 並列/分散アルゴリズム ) の主な活動は, 班会議を開催したことである.
第 1 回 A04班 班会議は, 次の日時および場所で行った.
昼食後, 「A04班の今後の活動について」話し合いが持たれた.
各チュートリアルの詳細および第 1 回 A04班 班会議の審議事項は,
成果報告書の「チュートリアル」「第 1 回 A04班 班会議議事録」を参照され
たい.
第2回 A04班 班会議は, 平成10年度第2回全体会議に合わせて, 次の日程および
場所で開催する予定である.
本研究グループの研究項目は離散最適化アルゴリズムであり,本特定領域研究
(B)「アルゴリズム工学」研究全体に深く関わるもので,他のグループとも密
接な関係をもちながら,A01班内ではこのテーマそのもののさらなる理論の深
化により一般性のある離散最適化理論の構築と,それに裏打ちされた実用アル
ゴリズムの開発を行なうことを目指している.ここでは,ニュースレターで班
を紹介するということで,主にA01班にある7つのグループの構成メンバと研究
テーマの紹介を行なっていく.これらの7つのグループが班全体として有機的
に共同研究を進めている様子については,本ニュースレターのA01班の初年度
報告に詳しく書かれているのでここでは繰り返しは述べない.
以下,A01班は7グループからなり,室田一雄班長のグループから始めて各グルー
プを紹介する.本文の文責は,副班長の今井浩にある.
Ninth Annual International Symposium on Algorithms and Computation
(ISAAC'98)は1998年12月14--16日の3日間, 韓国は大田(Taejon)のHotel Rivieraで
開催された. 日本からもこの特定領域研究の関係者を中心として非常に多くの参加者
があったが, 茨木俊秀先生(京都大学)と玉木久夫先生(明治大学), 周暁先生(東
北大学), 私の四名がこの科研費から旅費の補助をいただいて参加した.
大田はソウルから全席指定の特急セマウル号で約1時間半南下した所にあり, ガイド
ブックによると忠清南道の道庁所在地で人口120万人の大都市だそうだ. 韓国の冬は
寒いと聞いていたが, 到着してみるとさほどではなく, 地元の人間に
聞いてみると前日まで寒かったがその日から急に暖かくなったとのことだった. 確か
にどの建物も二重窓であることが普段の寒さを物語っている(日本じゃあ二重窓は北
海道ぐらいだもんね).
会場のリビエラホテルは大田の西方郊外の儒城温泉にある五つ星の最高級ホテル. 宿
泊室内にはオンドルが効いていて, これがとても暖かく, 夜なぞは毛布が要らない程
だった. 空調による暖房と違って風が当たったりすることも無いし, 日本もこの暖房
システムと二重窓を取り入れるべきだと思った(かなりの省エネが期待できる).
今回講演数は招待2件を含んで49件で, 2つのパラレルセッションがあった.
Stephan Eidenbenz氏は美術館問題(art gallery problem)における頂点監視(vertex
guard), 辺監視(edge guard), 点監視(point guard)の3問題が, どれもP≠NP
の前提において, ある実数ε > 0に対し1 + ε近似の多項式時間算法が存在し
ないことを証明していた. 証明法はMAXSNP完全であるsc 5-Occurrence-3-Sat
を帰着していたが, 視覚的で面白かった.
実用的な意味で興味を持ったのが, Boris Aronov氏らの提案した, 三角形の集まりで
表現された地平上での設備配置問題(1-center問題)に対する高速算法である. 最近
のコンピュータゲームは実時間でポリゴン画像を計算, 表示していくので, こういっ
たアルゴリズムが大いに役立つに違いない.
どの発表もさすがに水準が高く, こういう会議に出席するのは, やはり楽しい. 次回
はインドで12月16--18日に開催される予定だが, この日取りは我が学科の卒論発表日
(豊橋技科大は12月にやります)と見事に重なっているので次回は残念ながら来られ
そうに無いが, 今後もなるべく頻繁に参加し続けようと思っています.
第10回ACM-SIAM 離散アルゴリズムシンポジウム(SODA'99)は
アメリカ合州国メリーランド州ボルチモア市において
1月17日から19日にかけて開催された.
SODA'99は今年から新しい試みでlong paper(10ページ) とshort paper(
2ページ)に二つにわけたため従来の倍以上の数の講演があった.
より多くの参加者を集めようという主催者の意図であろう.
(なおこの試みは来年も継続されるそうである. ) その効果として
確かに多くの出席者があったため賑やかな感じがした.
しかし,4つのパラレルセッション,一件あたり発表時間
17分ということもあり,お祭りに近い印象も受けた.
また,論文の質という点でバラツキも見られた.
招待講演は, Scott Shenkerの ``Game Theory and Computer Networks'' と
Carsten Thomassen の ``A Second Hamiltonian Cycle'' の2件であった.
前者は, 情報化社会の急激な展開のなかに何とか理論的な研究課題を
見い出して, 貢献していこうとする計算理論コミュニティの最近の姿勢,
後者は, 知的興味を最大の価値基準とする離散数学の伝統的な研究姿勢を
それぞれ代表して, このシンポジウムの性格をよく反映していた.
Shenker の講演は絶妙な語り口で, 「ネットワークのプロトコルの
設計は, ユーザの生悪説に立って行なうべきで, 従ってゲーム理論に
基づかなければならない」という主張を可能な限りの説得力で論じたが,
これまでの結果から見る限りこのアプローチの有用性は未知数であると
感じられた. Carsten Thomassen の講演は, 彩色多項式のゼロ点との
関係から説きおこし, なぜ2番めのハミルトン閉路の存在が面白い問題
かということを十分に納得させる内容であった. しかしながら, 欲を言えば
招待講演のテーマとしては, 今少し迫力不足の感もあった.
一般講演は多岐多様にわたり, 傾向を総括するのは難しいが, 計算幾何の
セッションが7(全46セッション中)あったのは目をひいた.
一般講演は前述のように4本のパラレルセッションであることから
(さらに時差のハンディもあり), 一部しか聞くことができなかったので,
この印象は偏っている可能性があるが, 全体として驚くべき結果や斬新な
アイディアはそれほど見当たらず, かなり技術的な印象を受けた.
最後に, 報告者らの印象に残った講演を2, 3挙げる. これは報告者らの
個人的な興味に基づくもので, 講演や論文の優劣とは直接の関係が
ないことは言うまでもない.