TOKUTEI: algorithm News Letter No.4
特定ニュース VOL.4 MARCH 2000
目次
事務局
〒606-XXXX 京都市XX京区XXXX町
京都大学XXX研究科XXXX専攻
特定領域研究(B) 「アルゴリズム工学」事務局
担当: 永持 仁
電話: 075-XXX-XXXX FAX: 075-XXX-XXXX
E-mail: naga@XXXX.kyoto-u.ac.jp
URL: http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/

I.各班の活動状況, 各班の会議(講演等)の報告

1.A01班の活動状況

A01班の平成11年度の活動は, 班会議での研究会討議と検討会を通して, 全体での 有機的に連携した研究の推進を進めた. また, 各研究グループでの活発な研究 の促進も図られ, それが同時に全体での融合研究にも結び付いている. 具体的 には, A01班として次のような活動を行なった.

1.1.平成11年度第2回班会議

日時:平成11年10月29日(金)11:30--13:00
場所:京都大学数理解析研究所206号室(出席者15名)
(議事要旨) 次回班会議について検討を行い, アルゴリズムデータベー ス関係のプロジェクトを推進することについて検討した. また, 来年度国際会議への招聘候補者についても議論した.
1.2.平成11年度第3回班会議

日時:平成11年12月21日(火)10:00--16:20
場所:大阪大学吹田キャンパス医学部銀杏会館(出席者22名)
以下のプログラムで研究会を開催し, 熱心な討議が行われた.

10:00 - 10:50 牧野和久(大阪大) 『ハイパーグラフの部分横断と多重横断について』
茨木の問題とも呼ばれるハイパーグラフの極小横断の多項式時間列挙問題は有 名な未解決問題であり, 応用も広い. 本発表では, 横断の概念を一般化させた 部分横断, 多重横断を導入し, ハイパーグラフの極小部分横断(あるいは, 極 小多重横断)を列挙する問題が上記の問題に多項式時間還元可能であることに ついて述べた. また, 部分, 多重横断といった概念と知識発掘(data mining) における frequent set などとの関係を示した.
11:10 - 12:00 土村展之 (LOGOPT) 『データベース登録状況報告』
全体会議以降に進捗した web デモと, パッケージプログラムについてデモを 行い, また技術的な内容に踏み込んで現在のアルゴリズムデータベース登録状 況について説明がなされた.
14:20 - 15:10 市川周一 (豊橋技術科学大) 『並列計算における静的負荷分散』
並列計算における静的負荷分散は, 古くから“マルチプロセッサスケジューリ ング問題”として単純化され研究されてきた. 単純化された問題ですら計算困 難であるが, 現実的な並列処理では通信時間やデータ分割など多くの要素を考 慮しなければ役に立たない. 偏微分方程式の並列・分散処理に関して問題点を 検討した.
15:30 - 16:20 藤江哲也 (神戸商科大) 『線形化による半正定値計画緩和と線形計画緩和』
Lovasz, Schrijverは, 0-1整数計画問題に対する半正定値計画問題 および連続緩和よりも強力な線形計画問題による緩和を提案した. 半正定値計画緩和で線形化とよばれる方法は Lovasz, Schrijverの方法に関連するもので, 0-1整数計画・組合せ最適化問題 を含む広いクラスの問題に対して半正定値計画緩和・線形計画緩和を導くことがで きる.本発表では, 線形化および半正定値計画緩和・線形計画緩和の導出方法と 基本性質を与え, さらに, 個々の問題に適用して得られる結果について概観した.

また, 班会議を次のように開催した.

日時: 平成11年12月21日(火)12:00--12:50
場所: 大阪大学吹田キャンパス医学部銀杏会館(出席者12名):
(議事要旨) 2000年10月の全体会議での外国人招聘について, 各班2人程度招聘する必要があり, この件についてA01班の対応を検討した. 次回の全体会議について, A01班からの企画を決めた.
2.A02班の活動状況

主な研究対象は, 離散最適化問題の中でも基礎的でかつ広範な応用性を 持ったグラフ問題, ネットワーク問題, 充足可能性問題などである. A02班は, アルゴリズム工学の立場から, これらの諸問題に対する効率的な アルゴリズムの発見や計算量解析を行っている. また更に, そのためのグラ フ論的な分析や関連分野・テーマに関する研究も併せて行っている. 平成11 年度後半は, 以下のように班会議を開催し, 共通の目的意識を 形成するとともに, アルゴリズムデータベースの実現に向けて度重なる討議 を行った. なお, 平成11年度第5回班会議は3月10日(金)の12:00-13:00に開催予定.

2.1.平成11年度第3回班会議

出席者: 13名(浅野孝夫,宇野毅明,小野孝夫, 周暁,陳致中,築山修治, 戸田誠之助,永持仁,蓮沼徹,藤戸敏弘, 松井知己, 夜久竹夫, 渡邉敏正)
日時・場所: 1999年 10月29日(金)11:30-13:20,京都大学工学部8号館数理会議室
内容: 新規の共同研究者の紹介, 10月27日(水)の総括班会議の報告, 次回の班会議開催日(平成12年1月26日(水))の決定後, 以下の件について意見を交換した.
  1. A02班のアルゴリズムデータベースの構築に向けて
  2. 平成12年10月の全体会議に招聘する外国人研究者の候補者
1に関しては 平成12年3月をめどに, 各研究代表者から申し出のあったプログラムのうち半数を プログラムパッケージとして完成させるという目標について再確認を行った. 2に関しては後日, D.P.Williamson とJ.Cheriyan に決定した.

2.2.平成11年度第4回班会議

出席者: 15名(浅野孝夫, 宇野毅明, 草刈良至, 周暁, 武永康彦, 谷聖一, 陳致中, 土村展之, 戸田誠之助, 永持仁, 蓮沼徹, 平田富夫, 松井知己, 夜久竹夫, 山崎浩一)
日時:2000年1月26日(水)10:00-17:15
会場:電気通信大学 西9号館3階AVホール
内容:以下のプログラムに基づき, 研究成果を報告すると ともに各発表について討論を行った. 特に, 今回は, A03班 の研究分担者(山崎浩一氏)や本研究外の研究者(武永康彦氏) にも発表をお願いし, 各方面からの情報を提供して頂いた.
  1. 武永康彦(電通大) 『Recognition of Ordered Tree-Shellable Functions Based on OBDDs』
  2. 宇野毅明(東工大) 『A Speeding up Technique for Local Search on Vehicle Routing Problem with Soft Time Window Constraints』
  3. 戸ヶ崎 光敬, ◯山崎 浩一(群馬大) 『R上の proper 区間表現を Z上の unit 区間表現へ変換するアルゴリズム について』
  4. 平田富夫(名古屋大学) 『距離変換をつかったモルフォロジー演算の高速化について(デモ)』
  5. ○Hiroshi Nagamochi(京都大), Tibor Jordan(U.Aarhus), Yoshitaka Nakao(住友金属) and Toshihide Ibaraki(京都大) 『Convex Embeddings and Bisections of 3-Connected Graphs』
  6. 土村 展之 『データベース登録状況報告: web デモと, パッケージプログラムについて』

またさらに, 土村展之氏の発表をもとに, にアルゴリズムデータベースの現状と 技術上の問題点について詳細な議論を行った.

3.A03班活動状況

A03班の目的は, 幾何に関係する諸問題を効率的に解決する アルゴリズムを開発することと, それらの問題の本質的な計算 困難さを解析することにより, 近似アルゴリズムの妥当性を 示すことにある. 直接的に幾何データを取り扱う問題だけではなく, 入力は幾何に 関係がなくても, 解決の手段として幾何的な取り扱いが有効である 場合もあり, その守備範囲は広範である. そのためにともすると 個別研究の集まりとなってしまってアルゴリズム工学の趣旨に 反することにもなりかねないので, 定期的に会合を開いて共通の 方向を模索している. 共通のキーワードあるいは要素技術を 「三角形分割」と決めて, グループ内でのコラボレーションを 促進しようとしている. また, 共通の技術的基盤を確立するために A03班ではアルゴリズムの記述に適したLEDAに焦点を当て, できる限りLEDAでアルゴリズムを記述しようとしている. 現在, そのための準備を進めているところである. 具体的な 活動については, 本報告の後半で触れることにする.

3.1.平成11年度第4回会合

平成11年6月3,4日(木,金曜日)3日午後1時〜4日午後5時
場所:石川県文教会館(金沢市尾山町10-5)
参加者:浅野(哲夫),杉原厚吉,徳山豪,加藤直樹,今井桂子, 中野眞一,小保方幸二,山崎浩一,その他学生2名

本会合では,班の構成員から研究の進展状況について報告を受けると ともに,産業界における問題解決の事例を紹介してもらって, アルゴリズムの立場からどのような貢献が可能かを探ることを目的とした. 構成員からの報告としては, まず杉原から,計算幾何学における重要な概念であるミンコフスキー和の 逆演算とも言えるミンコフスキー差の新たな定義とその応用について説明が あり,活発な討論が展開された. 続いて,今井から,地理情報処理における典型的な問題である地図への ラベル貼り付けの問題について報告があった.白地図に県名や河川名などの 地名を貼り付ける問題については従来から盛んに研究されてきたが,工事などで 使われる引込線を用いた地図については今までに本格的な研究がなく,しかも 規則的な出力を要求されるという意味において今後アルゴリズムからの貢献が 期待されている分野である.特に,現実の地図が示され,参加者が実際の問題の 難しさを認識できた点が良かった.

中野からの報告も地図へのラベル貼り付けの問題であった.地図上にラベルを 交差なく貼り付ける問題はアルゴリズム的には非常に難しい問題であることが 多いが,ラベルの置き方にある種の制約を置くと,合理的な時間で解を得る ことができることを示した.緩い制約の下に近似解を求めて,交差を減らす ための後処理を考える従来の方法と比較して有利な点も多いと思われる. 徳山からも地理情報処理に関係する問題として,大規模な交差判定問題に 対して計算幾何学で開発された各種のアルゴリズムを適用した経験について 報告があった.計算幾何学で開発されたアルゴリズムは,漸近的な効率しか 保証されていないので,実際の問題に適用するときにはチューニングが必要で あるとの結論であった.チューニングを理論的に解析する方法が求められる. 加藤からは,多角形内部への点パッキング問題とメッシュ生成問題について 報告があった.従来,類似の研究が純粋に数学的な興味から研究されたことは あったが,建築学において実際的な応用があるという意味において,新たな 視点からの研究が必要とされていることがわかった. 浅野からは,同様のパッキング問題であるが,印刷技術への応用ということで 離散的な場合についての研究成果の一部の紹介があった.連続平面上の問題も もちろん難しいが,格子平面に限っても問題は易しくならないのは何故かが 紹介された.

産業界における問題解決の事例を紹介してもらうために,大日本スクリーン 製造(株)からも会合に参加してもらい,現実の問題の難しさについて具体的な 事例をあげて説明を受けた.問題の内容についてはここでは報告できないが, 幾何的最適化の問題として定式化できる問題であり,参加者から線形計画法, 分割統治法など,様々なアルゴリズム技法の可能性が指摘された.

3.2.平成11年度第5回会合

平成11年10月29日
場所:京都大学工学部8号館
参加者:杉原, 浅野, 加藤, 徳山, 玉木, 山崎, 小保方, 中野, 今井, 藤澤の10名
この会合では特にアルゴリズムデータベース関係に焦点を絞って議論を 行った. まず, 徳山先生から, アルゴリズムデータベースに提供できる ソフトの一覧に関する調査結果について報告があり, 今後具体的に 作業を進めていくこととなった.

3.3.平成11年度第6回会合

平成11年11月24日午前11時から午後5時
場所: 中央大学理工学部
参加者:杉原, 浅野, 加藤, 徳山, 玉木, 中野, 小保方, 今井, 他数名.
本会合では, 杉原(東京大学), 加藤(京都大学), 浅野(北陸先端大)の 3名が現在の研究の進展状況を話すという形式で進めたが, 単なる一方的な 講演に終わらないように, 講演の途中での質問を許すとともに, 今後の研究の 進展に向けて全体で意見を出し合うという形式を取った. 3件の講演の要旨は 次の通りである.

杉原厚吉(東京大学工学部計数工学科)「計算幾何学から見たメッシュ生成の現状と課題」
概要: 有限要素法などのボトルネックとなっているメッシュ構造の生成法の現状を 概観し, 今後の課題を整理した. 代表的なメッシュには, 2次元では, 3角形メッ シュと四角形メッシュがあり, 3次元では, 4面体メッシュと6面体メッシュがある. 2次元においては, どちらのメッシュもその生成法はほぼ完成しており, 多数の 実用的なソフトウエアもすでに利用されている. 一方, 3次元では問題は極端に 難しい. 四面体メッシュは, ドロネー分割を利用したものが, もっとも有力な方法と して開発されているが, 未だ, 良質のメッシュが得られるとは限らず, ドロネー分割 とは別の方法が探られている. また, 6面体メッシュは質のよいものを作るのがもっ とも難しく, 状況に応じた個別の工夫で作られるのがほとんどで, 汎用の方法で良質の メッシュをつくることはほとんどできていない. 最近では, メッシュが不十分だった り, あるいは, メッシュがなくても使える新しいタイプの有限要素法を開発しようという 試みもある.

田川浩(京都大学大学院工学研究科建築学専攻)「連続的トポロジー変化モデルを用いたトラスの形状最適化」
概要: 前半では, 平面トラスおよび立体トラスに対する連続的トポロジー変化モデル について説明した. このモデルは, 節点数, 部材数および節点間の接続関係など, 初 期に与えた情報を全く変更することなく, 連続的にトラスのトポロジーを更新してい くことを可能とする. 後半では, 連続的トポロジー変化モデルおよびシミュレーテッ ドアニーリング法を用いたトラス構造物の形状最適化手法を示し, 例題を通じて最適 化手法の特徴について説明した.

浅野哲夫(北陸先端科学技術大学院大学)「等高線表現に基づく画像の自然な拡大」
概要: 画像を拡大する方法としては3次関数による近似を用いたバイキュービック法 などが実用的には使われているようであるが, 倍率が高くなった場合には不自然な 模様が入るなどの問題がある. ここでは, 画素の明るさをその地点での標高とみな しことによって画像を地形図と同様に等高線で表現する方法に基づいた幾何的 手法を提案する. 基本的な考え方は, 等高線を滑らかな曲線で近似しておいて拡大を 行おうというものであるが, 等高線が本来もつべき性質を保持したままで拡大処理を 行うことにどのような難しさがあるかを指摘した後, contour tree, channel approximationなどの概念を導入することによって, この問題が制約を満たす形で 解けることを示す.

4.A04班の活動状況

本年度後期の A04 班の主な活動は, 平成 11 年度第 1 回全体会議のときに行われた 第 5 回班会議, 平成 11 年度第 2 回全体会議と同時に開催される予定の 第 6 回班会議および平成 11 年度第 2 回全体会議で予定されている講演である. それらの概略(予定を含む)記す.

4.1.A04班 第5回班会議

日時:平成 11 年 10 月 29 日(金) 11:40 〜 13:10
場所:京都大学 工学部 8 号館 2 階 中会議室
出席者:15 名
審議事項
  1. 海外招聘について
  2. アルゴリズムのデータベース化について
  3. 3 月に開催される予定の全体会議での講演について
  4. 日韓合同アルゴリズムワークショップのお知らせ
4.2.A04班 第6回班会議(予定)

日時:平成 12 年 3 月 10 日(金) 10:30 〜 12:00
場所:金沢文化ホール
議題
  1. 平成 12 年度の活動について
  2. アルゴリズムのデータベース化について
4.3. 第 2 回 全体会議 特別セッション(予定)

平成 11 年度 第 2 回 全体会議 特別セッションにて, 次の 2 件の 報告が予定されている.

梅本 潤, 河合 大輔, 宮崎 修一, 岡部 寿男, 岩間 一雄 (京都大学大学院 情報学研究科) SAT局所探索の並列化
概要: 充足可能性問題に対して近年開発された局所探索法というアルゴリズムを, ベクトル化とPVMを使うことにより並列化し, 1秒あたりの探索回数を従 来の600倍にまで向上させた. これまで解かれていなかったDIMACSベンチマー ク例題を, 我々のアルゴリズムにより世界で初めて解くことに成功した.
山下雅史(九州大学大学院 システム情報科学研究科) 分散環境における並列計算を支援するシステム
概要: 分散環境を用いた並列計算自体は良く研究された概念であり原 理的には取り立てて新たに検討すべき点はないようにも思われる が, 数100 〜 数1000台規模の計算機を用いて数週間〜数ヵ月 に渡る長期の計算を一般のユーザが行なうのを支援することを 目的に据えると様々な検討課題が現れる. 本プロトタイプの製作 目的は今後検討すべき課題を明らかにすることであるが, 直接的 には, 次に述べる課題に対して暫定的な解決法を与え, その効果 を評価することにある:
  1. 問題解決に適した計算環境の構築
  2. 動的な負荷分散
  3. 故障からの回復

II.シリーズ:研究班の紹介 - その3 -

A03班「幾何アルゴリズム」の紹介

我々が3次元ユークリッド空間で生活していることを考えると, 幾何的制約をもった組合わせ最適化問題の解決が求められる場面は多い. 本研究項目では,このような幾何的制約を処理するアルゴリズムを研究する. 幾何アルゴリズムの特徴は,連続空間を扱うことによる困難さと幾何的制約の有効利用の可能性にある. 本研究グループは幾何アルゴリズムというキーワードで統一されているものの, 個々の研究テーマは多岐にわたっており,手法的にも様々である.そこで, 本グループではグループ内での共同研究を促進するために,共通の話題を三角形分割に定め, ここを中心にして展開を図っている. また,アルゴリズム工学の観点からアルゴリズムの実装にも力を注ぎ,アルゴリズム実装手段として ドイツで開発されたアルゴリズムライブラリ兼アルゴリズム記述言語でもあるLEDAでの実装を通して ソフトウェア資源の共有化と社会への公開に努力している. 実際に共同研究は着実に進行しており,具体的な成果も得ている(具体的な 例については3月に報告予定のA03班研究成果報告を参照されたい).以下に各グループを紹介する.

研究課題: 精度保証機能をもった幾何アルゴリズムの構成法

研究代表者:
杉原厚吉(東京大学大学院工学系研究科)
研究分担者:
速水 謙(東京大学大学院工学系研究科)
山本修身(青森大学工学部)
今井敏行(和歌山大学システム工学部)
西田徹志(東京大学大学院工学系研究科)
研究内容: 本研究グループは, アルゴリズム工学の諸側面のうちで, 幾何アルゴリズム において特に深刻な, 計算精度の有限性が原因となって生じる理論的アルゴリズムと 現実的ソフトウエアの間の溝の問題に着目し,それを埋める努力をしている. 特に, その解決のために, 厳密計算と記号摂動を組み合わせるというアプローチに焦点をあて, ソフトウエア設計のための方法論の確立と, その具体的アルゴリズムへの適用を行っている. 現在までに,2次元ボロノイ図,3次元ドロネー図, 4次元凸包などの基本的幾何データ 構造の生成アルゴリズムをこの方法を適用して実装した. また, この方法で作ったメッシュ を利用するための, 偏微分方程式の数値解法の数値的安定化や高速化も研究して いる. さらに, 厳密計算に必要な精度を保証するための精度評価方法を, 多項式の 零点不在領域の解明という観点から解析したり,退化回避のための記号摂動法の 完全自動化をグレブナ基底を利用して実現する方法を模索したりもしている.

研究課題: 理論的には計算困難な問題の現実的解法に関する研究

研究代表者:
浅野哲夫(北陸先端科学技術大学院大学情報科学研究科)
研究分担者:
徳山豪(東北大学大学院情報科学研究科)
小保方幸次(北陸先端科学技術大学院大学情報科学研究科)
研究内容: 従来,アルゴリズム理論の分野ではアルゴリズムの漸近的な 振舞いに関心が集中しすぎて,現実に存在する問題の解決を図るという 工学の基本をおろそかにしていた傾向がある. 現実問題の数学的モデル化から取り組み,その 理論的な計算複雑度の解析,更に近似解法を含めた実用的なアルゴリズム設計までの 全工程を考察することにより問題解決を試みる必要がある. 本研究グループでは画像処理を中心に実用上重要な現実問題を取り上げ, このアプローチの有効性を実証することを最終的な目標としている. 具体的には,以下のような研究を行っている. (1) 多レベルのカラー画像を8色だけで近似するハーフトーニングを 組合わせ最適化問題として定式化し,それがNP完全であることを証明した 後で,最適解との誤差をある定数で抑えることが可能な近似解法などを 開発した.(2) エッジ検出後の2値画像に含まれる直線成分を検出する 問題を数学的に定式化して,その本質的な計算複雑度を解析した後で, 現実的な高速のアルゴリズムを開発し,計算機上に実装した.(3) 集合 切り出しとクラスタリングについても,上述のアプローチに基づいて, 従来は最適化が不可能だと思われていた問題にも取り組んでいる.

研究課題: グラフの高品質描画アルゴリズム

研究代表者:
中野眞一(群馬大学工学部)
研究分担者:
山崎浩一 (群馬大学工学部)

研究内容: 様々な情報をグラフによりモデル化することは広く行われているが, グラフにモデル化された情報をユーザがGUIを用いて効率的に理解・探索・ 操作etc.するためには, グラフを様々な意味で"適切に"描画する必要がある. グラフ描画問題は, 多くの場合, いくつかの"適切さの尺度"を尺度間の優先順位を考慮しつつ最適化する問題として 定式化される. しかしながら, 現状では, これらの最適化問題には高速に解く方法が知られていないものや, 理論的には高速であるがプログラミングが極めて難しいものが多い. 本研究グループでは, これらの問題を解く簡単な方法の開発, グラフの 様々な"適切な"描画を高速に求める汎用のプログラムの開発, および, 関連する問題の研究を行なう. これまでに理論的ないくつかの成果を得ており,さらに, グラフ描画システムを作成中である.このうち,グラフエディタがほぼ完成している. グラフの平面埋め込みを求めるjava class等を現在実装中である. http://www.msc.cs.gunma-u.ac.jp/nakano_lab/project からプログラムを起動可能であるので,バグ報告や機能改善の提案を歓迎する.

研究課題: 建築計画・建築構造における幾何学的アルゴリズムの開発

研究代表者:
加藤 直樹(京都大学工学研究科)
研究分担者:
大崎 純(京都大学工学研究科)
田川 浩(京都大学工学研究科)
藤澤 克樹(京都大学工学研究科)

研究内容:}本研究グループでは次の4つのテーマに関する研究をおこなった. いずれも計算幾何学,数理計画に関する最新の理論的成果やアルゴリズムを 建築分野へ応用したものである.

  1. 曲面構造物の最適メッシュ近似
  2. 建築画像の消失点検出手法の開発と3次元建築モデル再構成手法
  3. 二目的複数施設配置問題の解法
  4. 半正定値計画法による構造物の最適設計法
1については新しい近似尺度を導入して, 精度保証のある近似解法を提案している. 3についてはパレート最適解 の存在位置の新しい幾何的性質をもとにパレート解集合を求める アルゴリズムを提案している. 4では,半正定値計画法に基づいていくつかの 構造最適化問題に対して従来手法の困難な点を解消する新しい手法を提案している. また,これらのテーマは単に既知の成果を建築分野に応用したと いうことにとどまらず, 計算幾何学,数理計画における新しい問題提起をおこなっている.

研究課題: 経路最適化問題の近似アルゴリズム: 幾何学的制約の有効利用と 大規模問題に対する実用化

研究代表者:
玉木久夫

研究内容:巡回セールスマン問題や最小シュタイナー木問題などのように, 辺に長さが割り当てられたグラフの定められた形の部分グラフで最短のものを 求める問題の多くはNP困難である. グラフの頂点を空間上の点, 辺の 長さを幾何的距離とすることで, これらの問題は自然な幾何版に特殊化されるが, その場合でも正確な最適値を求める問題は依然としてNP困難である場合が多い. しかし, これらの問題は, 小さい正定数$\epsilon$に対して 正確な解の$(1 + \epsilon)$倍以内近似解を求めることを目的とするならば 多項式時間で解けることが最近明らかになって来た. 今のところ, これらの アルゴリズムは多項式時間とは言え指数の定数($\epsilon$に依存する)が 非常に大きいため, 実用にはほど遠いと考えられている. 本研究では, これらのアルゴリズムをベースにして, 現実に高速で高性能の アルゴリズムの実装を行うことを目的としている. ここで, 理論的な 保証には必ずしもこだわらない. 現在までに, 平面上巡回セールスマン 問題に対するAroraの近似アルゴリズムの実装を行い, 様々な高速化, 高性能化 のためのアイディアを実験しているところである.

研究課題: 動的および実時間環境における幾何構造の変化に対する統一的手法に関する研究

研究代表者:
今井桂子(中央大学理工学部情報工学科)

研究内容:地理情報処理,移動体通信などの技術の進歩から,離散的な問題に 対して,その構造が時間と共に動的に変化していく場合や,これから先に与えられる データに関する情報がない状態で実時間的に問題を解かなければならない状況が 現れてきている.本研究では離散構造のうち幾何構造に着目し,このような 問題に対する統一的手法に関する研究を行なっている.1つのアプローチとして, 基本的な幾何的データ構造である三角形分割に対して, これまで静的な場合に得られているアルゴリズムの動的・実時間環境への拡張を 探っている.また, 地理情報処理における重要かつ実用的にも必要とされているラベル配置問題に対して, 多角形を配置する問題として幾何的に扱うことができることから, 幾何的アルゴリズムを用いて解く試みを行なっており,路線図などの実際のデータを 用いた実験を行なっている.


III.国際会議参加報告

Graph Drawing'99
西関 隆夫 (東北大学大学院情報科学研究科)

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日に開催される.

IEEE FOCS'99
徳山 豪 (東北大大学院情報科学研究科)

第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年前近郊に住んでいた)に歩いてみると清潔で綺麗, かつ安全そうな都会に一変していた. 以前たくさん見かけた麻薬中毒者みたいな浮浪者が全然居ない. これもアメリカの好景気のおかげで, やっぱり経済は大切である(バブルが弾けないと良いけど). 知り合いの(元)学生たちも多くは良い職を得て嬉しそうであった. 「やっぱり活気があるのは良いや」というのが私の感想であった.

ISAAC'99
牧野 和久 (大阪大学大学院基礎工学研究科)
堀山 貴史 (奈良先端科学技術大学院大学情報科学研究科)

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の開催地はアジア・オセアニア地域であったが, 台湾, ニュージー ランドを経てカナダでの開催も計画されているとのことで, 今後も講演者として 参加していきたい.

SODA'2000
加藤 直樹 (京都大学工学部)

第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$\%づつの改良が見られるそうです. よくも飽きることなく一つのテーマで 次々と新しい結果が出せるものだと感心した次第です. 研究に対する姿勢として 見習いたいと思いました.


IV.今後の全体会議等の予定

平成12年度第1回全体会議
日時: 平成12年10月(詳しい日時は未定)
場所: 京都大学数理解析研究所

趙 亮
<最終更新作成日時 2000年7月5日 >