1.A01班の活動状況
A01班の平成11年度の活動は, 班会議での研究会討議と検討会を通して, 全体での 有機的に連携した研究の推進を進めた. また, 各研究グループでの活発な研究 の促進も図られ, それが同時に全体での融合研究にも結び付いている. 具体的 には, A01班として次のような活動を行なった.
1.1.平成11年度第2回班会議
また, 班会議を次のように開催した.
主な研究対象は, 離散最適化問題の中でも基礎的でかつ広範な応用性を 持ったグラフ問題, ネットワーク問題, 充足可能性問題などである. A02班は, アルゴリズム工学の立場から, これらの諸問題に対する効率的な アルゴリズムの発見や計算量解析を行っている. また更に, そのためのグラ フ論的な分析や関連分野・テーマに関する研究も併せて行っている. 平成11 年度後半は, 以下のように班会議を開催し, 共通の目的意識を 形成するとともに, アルゴリズムデータベースの実現に向けて度重なる討議 を行った. なお, 平成11年度第5回班会議は3月10日(金)の12:00-13:00に開催予定.
2.1.平成11年度第3回班会議
2.2.平成11年度第4回班会議
またさらに, 土村展之氏の発表をもとに, にアルゴリズムデータベースの現状と 技術上の問題点について詳細な議論を行った.
3.A03班活動状況
A03班の目的は, 幾何に関係する諸問題を効率的に解決する アルゴリズムを開発することと, それらの問題の本質的な計算 困難さを解析することにより, 近似アルゴリズムの妥当性を 示すことにある. 直接的に幾何データを取り扱う問題だけではなく, 入力は幾何に 関係がなくても, 解決の手段として幾何的な取り扱いが有効である 場合もあり, その守備範囲は広範である. そのためにともすると 個別研究の集まりとなってしまってアルゴリズム工学の趣旨に 反することにもなりかねないので, 定期的に会合を開いて共通の 方向を模索している. 共通のキーワードあるいは要素技術を 「三角形分割」と決めて, グループ内でのコラボレーションを 促進しようとしている. また, 共通の技術的基盤を確立するために A03班ではアルゴリズムの記述に適したLEDAに焦点を当て, できる限りLEDAでアルゴリズムを記述しようとしている. 現在, そのための準備を進めているところである. 具体的な 活動については, 本報告の後半で触れることにする.
3.1.平成11年度第4回会合
本会合では,班の構成員から研究の進展状況について報告を受けると ともに,産業界における問題解決の事例を紹介してもらって, アルゴリズムの立場からどのような貢献が可能かを探ることを目的とした. 構成員からの報告としては, まず杉原から,計算幾何学における重要な概念であるミンコフスキー和の 逆演算とも言えるミンコフスキー差の新たな定義とその応用について説明が あり,活発な討論が展開された. 続いて,今井から,地理情報処理における典型的な問題である地図への ラベル貼り付けの問題について報告があった.白地図に県名や河川名などの 地名を貼り付ける問題については従来から盛んに研究されてきたが,工事などで 使われる引込線を用いた地図については今までに本格的な研究がなく,しかも 規則的な出力を要求されるという意味において今後アルゴリズムからの貢献が 期待されている分野である.特に,現実の地図が示され,参加者が実際の問題の 難しさを認識できた点が良かった.
中野からの報告も地図へのラベル貼り付けの問題であった.地図上にラベルを 交差なく貼り付ける問題はアルゴリズム的には非常に難しい問題であることが 多いが,ラベルの置き方にある種の制約を置くと,合理的な時間で解を得る ことができることを示した.緩い制約の下に近似解を求めて,交差を減らす ための後処理を考える従来の方法と比較して有利な点も多いと思われる. 徳山からも地理情報処理に関係する問題として,大規模な交差判定問題に 対して計算幾何学で開発された各種のアルゴリズムを適用した経験について 報告があった.計算幾何学で開発されたアルゴリズムは,漸近的な効率しか 保証されていないので,実際の問題に適用するときにはチューニングが必要で あるとの結論であった.チューニングを理論的に解析する方法が求められる. 加藤からは,多角形内部への点パッキング問題とメッシュ生成問題について 報告があった.従来,類似の研究が純粋に数学的な興味から研究されたことは あったが,建築学において実際的な応用があるという意味において,新たな 視点からの研究が必要とされていることがわかった. 浅野からは,同様のパッキング問題であるが,印刷技術への応用ということで 離散的な場合についての研究成果の一部の紹介があった.連続平面上の問題も もちろん難しいが,格子平面に限っても問題は易しくならないのは何故かが 紹介された.
産業界における問題解決の事例を紹介してもらうために,大日本スクリーン 製造(株)からも会合に参加してもらい,現実の問題の難しさについて具体的な 事例をあげて説明を受けた.問題の内容についてはここでは報告できないが, 幾何的最適化の問題として定式化できる問題であり,参加者から線形計画法, 分割統治法など,様々なアルゴリズム技法の可能性が指摘された.
3.2.平成11年度第5回会合
3.3.平成11年度第6回会合
4.A04班の活動状況
本年度後期の A04 班の主な活動は, 平成 11 年度第 1 回全体会議のときに行われた 第 5 回班会議, 平成 11 年度第 2 回全体会議と同時に開催される予定の 第 6 回班会議および平成 11 年度第 2 回全体会議で予定されている講演である. それらの概略(予定を含む)記す.
4.1.A04班 第5回班会議
平成 11 年度 第 2 回 全体会議 特別セッションにて, 次の 2 件の 報告が予定されている.
A03班「幾何アルゴリズム」の紹介
我々が3次元ユークリッド空間で生活していることを考えると, 幾何的制約をもった組合わせ最適化問題の解決が求められる場面は多い. 本研究項目では,このような幾何的制約を処理するアルゴリズムを研究する. 幾何アルゴリズムの特徴は,連続空間を扱うことによる困難さと幾何的制約の有効利用の可能性にある. 本研究グループは幾何アルゴリズムというキーワードで統一されているものの, 個々の研究テーマは多岐にわたっており,手法的にも様々である.そこで, 本グループではグループ内での共同研究を促進するために,共通の話題を三角形分割に定め, ここを中心にして展開を図っている. また,アルゴリズム工学の観点からアルゴリズムの実装にも力を注ぎ,アルゴリズム実装手段として ドイツで開発されたアルゴリズムライブラリ兼アルゴリズム記述言語でもあるLEDAでの実装を通して ソフトウェア資源の共有化と社会への公開に努力している. 実際に共同研究は着実に進行しており,具体的な成果も得ている(具体的な 例については3月に報告予定のA03班研究成果報告を参照されたい).以下に各グループを紹介する.
研究課題: 精度保証機能をもった幾何アルゴリズムの構成法
研究課題: 理論的には計算困難な問題の現実的解法に関する研究
研究課題: グラフの高品質描画アルゴリズム
研究内容: 様々な情報をグラフによりモデル化することは広く行われているが, グラフにモデル化された情報をユーザがGUIを用いて効率的に理解・探索・ 操作etc.するためには, グラフを様々な意味で"適切に"描画する必要がある. グラフ描画問題は, 多くの場合, いくつかの"適切さの尺度"を尺度間の優先順位を考慮しつつ最適化する問題として 定式化される. しかしながら, 現状では, これらの最適化問題には高速に解く方法が知られていないものや, 理論的には高速であるがプログラミングが極めて難しいものが多い. 本研究グループでは, これらの問題を解く簡単な方法の開発, グラフの 様々な"適切な"描画を高速に求める汎用のプログラムの開発, および, 関連する問題の研究を行なう. これまでに理論的ないくつかの成果を得ており,さらに, グラフ描画システムを作成中である.このうち,グラフエディタがほぼ完成している. グラフの平面埋め込みを求めるjava class等を現在実装中である. http://www.msc.cs.gunma-u.ac.jp/nakano_lab/project からプログラムを起動可能であるので,バグ報告や機能改善の提案を歓迎する.
研究課題: 建築計画・建築構造における幾何学的アルゴリズムの開発
研究内容:}本研究グループでは次の4つのテーマに関する研究をおこなった. いずれも計算幾何学,数理計画に関する最新の理論的成果やアルゴリズムを 建築分野へ応用したものである.
研究課題: 経路最適化問題の近似アルゴリズム: 幾何学的制約の有効利用と 大規模問題に対する実用化
研究内容:巡回セールスマン問題や最小シュタイナー木問題などのように, 辺に長さが割り当てられたグラフの定められた形の部分グラフで最短のものを 求める問題の多くはNP困難である. グラフの頂点を空間上の点, 辺の 長さを幾何的距離とすることで, これらの問題は自然な幾何版に特殊化されるが, その場合でも正確な最適値を求める問題は依然としてNP困難である場合が多い. しかし, これらの問題は, 小さい正定数$\epsilon$に対して 正確な解の$(1 + \epsilon)$倍以内近似解を求めることを目的とするならば 多項式時間で解けることが最近明らかになって来た. 今のところ, これらの アルゴリズムは多項式時間とは言え指数の定数($\epsilon$に依存する)が 非常に大きいため, 実用にはほど遠いと考えられている. 本研究では, これらのアルゴリズムをベースにして, 現実に高速で高性能の アルゴリズムの実装を行うことを目的としている. ここで, 理論的な 保証には必ずしもこだわらない. 現在までに, 平面上巡回セールスマン 問題に対するAroraの近似アルゴリズムの実装を行い, 様々な高速化, 高性能化 のためのアイディアを実験しているところである.
研究課題: 動的および実時間環境における幾何構造の変化に対する統一的手法に関する研究
研究内容:地理情報処理,移動体通信などの技術の進歩から,離散的な問題に 対して,その構造が時間と共に動的に変化していく場合や,これから先に与えられる データに関する情報がない状態で実時間的に問題を解かなければならない状況が 現れてきている.本研究では離散構造のうち幾何構造に着目し,このような 問題に対する統一的手法に関する研究を行なっている.1つのアプローチとして, 基本的な幾何的データ構造である三角形分割に対して, これまで静的な場合に得られているアルゴリズムの動的・実時間環境への拡張を 探っている.また, 地理情報処理における重要かつ実用的にも必要とされているラベル配置問題に対して, 多角形を配置する問題として幾何的に扱うことができることから, 幾何的アルゴリズムを用いて解く試みを行なっており,路線図などの実際のデータを 用いた実験を行なっている.
Graph Drawing Workshopはグラフ描画に関するワークショップであり, 1993年から毎年開催されている. その第7回に当たるGD'99は 1999年の9月15日から19日までチェコのStirin城にて開催された. Stirin城はプラハから車で30分位の郊外にあり, 中世の城を国際会議にも使えるように最近改修されており, 客室も一流ホテル並みにきれいで快適でした. Stirin城にはゴルフ場もあり, 会場の脇には多くのゴルファーが見られたが, 会議参加者でゴルフを楽しんだ方はいなかったようだが, 散歩をする人々は沢山いた.
今年のGraph Drawingでは38件の一般講演と次の3件の招待講演があった. まず初日にJ. Matousekが計算幾何学の最近のトピックスについて講演した. 2日目にR. Thomasが``Graph Planarity and Related Topics"という演題で, 4色定理の新しい証明法などについて講演した. 最終日には, 数学者でかつ画家でも あるJ. Nestrilが``Art of Drawing" という演題で, 多くの絵をスライドで見せながら, 楽しい芸術的な講演をした.
一般講演で扱われたトピックスは, 直交描画, グラフラべリング, 3次元直交描 画, 階層平面埋込み, 円弧描画, 4連結平面グラフの格子描画, 交差最小描画, 対称性検出, 木のボロノイ図描画, 描画システムなどである. 論文集はSpringerの Lecture Notes in Computer Scienceの1冊として近々刊行される.
グラフ描画コンテストも行われ, 前もって与えられたグラフをいかに上手に 見易く描画できるかを競い, 優秀作品が選ばれた.
チェコと言えばビールが有名でうまく, しかも安い. 歓迎パーティー, バンケッ ト, 昼食時などでおいしいビールが沢山飲めた. コンサートも催され, プラハの音楽家によって多くの種類の笛の演奏が行われた.
Graph Drawing 2000は米国のWilliamsburgにおいて9月20日〜23日に開催される.
第40回IEEE FOCS (40th Annual Symposium on Foundations of Computer Science)は1999年10月17日から19日までニューヨーク市で開催された. 会場のペンシルベニアホテルは, マディソンスクエアガーデンの 向かいという絶好のロケーション. 好景気のせいであろうか, 会場の雰囲気は明るく, 参加者も多く活発であった.
P. Shor の量子計算による因数分解(1994), S. AroraのユークリッドTSP(1996)や 確率的証明チェック(1992), あるいは戸田さんの $PP \not\subseteq PH$ (1989) のように, 分野外の人にもショックを与えるような発表が でるのがこのFOCSである. 残念なことに, 今回はそのようなインパクトの結果は 見つからなかった(私の不見識かもしれない)のだが, 世界中から一流の結果が集まり(発表67件投稿218件), その中で アルゴリズム工学のプロジェクトメンバーからは 私と加藤さん(京都大学)の組み合わせ幾何学の論文 と陳さん(東京電機大学)のグラフアルゴリズムの論文 の2件が発表された.
トピックは多種多様であるが, 近年の風潮で, 実用上重要そうなNP完全問題の近似アルゴリズム設計 の論文が一番多い. 中でもクラスタリングに関連した近似手法の 発表は, データベースやインターネット検索など実用プロジェクトとの 関連が深いためか, これだけで5−6件あった. テクニカルにはグラフアルゴリズムや計算幾何学の延長で, n個のデータにk通りのラベルを付ける問題(E. Tardos の発表)を例に取ると, データ間の共通性を示すグラフと データとラベルの相性を表すテーブルから 計算されるコスト関数を最小にするラベル付けを行うのだが, 問題がマルコフランダム場やMultiway Cutなどの一般化になっていることを踏まえて 近似アルゴリズムの設計を行う. 近似比は $O( \log k \log \log k)$で お世辞にも良くは無いのだが, いろいろと改良や特殊化による 派生研究の可能性があり, その点で私には面白かった.
もう一つ目立ったトピックはランダムウォークなど確率過程の解析と その応用であり, 0-1ナップザックの解の数を数える全多項式近似ランダムアルゴリズム の設計などは評判が良かった. 私の専門(?)の計算幾何学では T. Chanによる凸包の動的管理の論文が非常にセンス良く出来ていたと思う. また, 学習理論の研究では ガウス分布の重なりを学習する論文などがあり, これは実用面からも重要そうであった. もちろん暗号や計算下界, オンラインアルゴリズムや量子計算 など, 各セッション活発であった.
招待講演として, マイクロソフト研究所に最近移ったL. Lovasz によるKnuth Prize受賞講演があり, グラフの 幾何学的実現とその応用の少し古い話をしていた. 会議当日はフムフムと聞いていたのだが, 今(12月末)になってみると 何も覚えていない(すみません). ただ, 私自身の講演が Lovaszの補題(世に言うLocal Lemmaではない) 云々というタイトルであり, これは当人が居てはやりにくいものであった. それはさておき, マイクロソフトが 理論グループの組織に取り組み始めたことは朗報と言えると思う (もっとも, Lovaszやフィールズ賞を取ったFreedmanなど 有名人が多い割にまだ小さい). 会場費の高いニューヨークで開催できたのも マイクロソフトとAT&T,IBMのスポンサーのおかげである.
最後になるが, ニューヨークを 久しぶり(7年前近郊に住んでいた)に歩いてみると清潔で綺麗, かつ安全そうな都会に一変していた. 以前たくさん見かけた麻薬中毒者みたいな浮浪者が全然居ない. これもアメリカの好景気のおかげで, やっぱり経済は大切である(バブルが弾けないと良いけど). 知り合いの(元)学生たちも多くは良い職を得て嬉しそうであった. 「やっぱり活気があるのは良いや」というのが私の感想であった.
Tenth Annual International Symposium on Algorithms and Computation (ISAAC'99)は1999年12月16--18日の3日間, インドのチェンナイ(旧称マドラス)で 開催された. 日本からも, この特定領域研究の関係者を中心として非常に多くの参 加者があった. 牧野, 堀山の2名も, この科研費から旅費の補助をいただいて参加 した. ISAAC'99と前後して, 13--15日にFST\&TCS 99 (Foundations of Software Technology and Theoretical Computer Science)が, 19--20日にIIT (Indian Institute of Technology)で近似アルゴリズムに関するワークショップが, それぞ れ開催された. インドに行くまでに研究室の学生さん(インド経験者)にさんざん怖 い話を聞かされていたためか, それともチェンナイ空港を出たとたんにインド人の 群衆の鋭い視線が突き刺さってきたためか, インド到着時にはずいぶん緊張をして いた事を覚えている. しかし, 空気を吸っている内に(それなりに)環境に適応でき るようで, 当初は無実序に見えた車と人と牛の流れからインド版交通ルールを見つ けたりしていた.
さて, ISAAC'99の講演数は招待講演3件を含む43件あり, 一般講演は2つのパラレル セッションで行われた. Prof. Kurt Mehlhornの``The Engineering of Some Bipartite Matching Programs''と題した招待講演では, LEDAのマッチング問題への 適用を例にとり, 正にアルゴリズム工学の重要性が説かれた. また, Prof. Eva Tardosの``Approximation Algorithms for Some Clustering and Classification Problems''は, クラスタリング問題の近似的解法について, 画像処理への応用例を 示しつつの講演であった. 杉原厚吉先生の``Topology-Oriented Approach to Robust Geometric Computation''は, 数値誤差のある計算機上で位相情報の正しさを保証す る幾何アルゴリズムについてであった. アルゴリズムを設計するための考え方が, 実行例を交えてわかり易くかつ面白く説明された. 一般講演でも, Approximate AlgorithmやComplexity Theoryの分野を中心に, 興味を覚えた講演が多々存在した.
これまでのISAACの開催地はアジア・オセアニア地域であったが, 台湾, ニュージー ランドを経てカナダでの開催も計画されているとのことで, 今後も講演者として 参加していきたい.
第11回ACM-SIAM 離散アルゴリズムシンポジウム(SODA2000)は アメリカ合州国カリフォルニア州サンフランシスコ市において1月9日から11日 にかけて開催された. SODA2000は, 昨年と同様の試みを踏襲して論文募集を long paper(10ページ) とshort paper( 2ページ)に二つに分けて行なった. long paperは247編の応募があり, 100編がacceptされ, short paperでは 88編の応募があり, 23編がacceptされた. 昨年は, long paper でrejectされた論文から, short paperに回された論文が相当数あったが, 今年はこれを無くして全く別々にした. その意図はDiscrete Mathematics の分野の論文の投稿を推進することにあるようである. この分野の人達は 10ページのアブストラクトを書くことに慣れていないことが主たる理由である. しかし, 意図したほど, Discrete Mathematicsの論文は集まらなかった. Business meetingでもこの点も含めて次回以降どのような方向・スタイルで SODAを進めて行くのかということが熱心に議論された. 結局, 今回を含めて2回行なった long paper, short paperの2種類に分けて論文募集をおこなう方針を, 次回も 続行することが確認されたが, 議論の過程ではさまざまな意見が出た. SIAMの事務局としては多くの参加者を集めることができたので良かったという 率直な意見もある.
会議は3つのパラレルセッション, 一件あたり発表時間 20分というスタイルで 進められた. 招待講演は, Robin ThomasのDigraph Minors and Algorithms, Vasek Chvatal の Cutting Planes and the Traveling Salesman Problem, Gene Myersの The Whole Genome Assembly of Drosophiaの3件であった. Thomas氏の話は大変面白かった. graph minorに関するRobertson and Seymour の有名な結果のさまざまなインパクトなどを熱い語り口で紹介された. Chvatal氏の講演は例によってジョークたっぷりで内容はさておき, 面白く聞かせてもらった. 最後のMyers氏であるが, 最近ニュースでよく 出て来る遺伝子解析で有名なCelera Genomics社においておこなった ショウジョウバエの遺伝子列の解析の話が中心であった. 内容は よく分からなかったが, アルゴリズムの人達がこのような分野で活躍している というのは, アルゴリズム分野に活気を与えているというのが 実感できたのはよかった.
私が聞いた講演の中から興味のある話を2つほど紹介しておきます.
E. Althaus and K. Mehlhorn: TSP-based curve reconstruction in polynomial time 点集合のデータ(画像のエッジ点)が与えられたとき, それをよく近似する 閉曲線を求める問題で, 昔から研究はされているのですが, ここではかなり 一般的な仮定の下で点集合のTSPを求めることで曲線が再構成できるという 話です. 特に興味深いのはそのTSPが多項式時間で求まるというところです. LP緩和問題にいつでも整数最適解があるという証明です. LEDAを使っていて この現象に気付いて証明してみたという話です. Mehlhorn先生が昨年日本に 来られたときにこの話も一部でされていたので, ご存知の方もおられる かも知れません.
G. Robins and A. Zelikovsky: Improved Steiner tree approximation in graphs, 無向グラフのスタイナー最小木問題の近似比をさらに改良したという話です. Zelikovsky氏等が中心になって最近(といっても10年前位), 次々と 近似比を改良していっているので, 内容的にはまたかという話ですが, 1年につき $2\sim 3$\%づつの改良が見られるそうです. よくも飽きることなく一つのテーマで 次々と新しい結果が出せるものだと感心した次第です. 研究に対する姿勢として 見習いたいと思いました.