１．A01班の活動状況

平成11年度の前半においては，6月に班会議を東京で開催し，次回はA01班は全 体会議の際に各々班会議を同時に開催し，12月に大阪でも開催する予定である． 以下，研究活動を具体的に述べる．

１．１．平成10年度第1回班会議

日時：平成11年6月24日(木) 10:00-17:00

場所：東京大学山上会館002号室

出席者リスト（順不同；３１名）：

室田一雄(班長), 茨木俊秀, 田村明久, 柳浦睦憲, 藤沢克樹, 降旗大介(京都 大学),石井博昭, 藤重悟, 岩田覚, 斉藤誠慈, 浜邦彦 (大阪大学),久保幹雄 (東京商船大),伊藤大雄(豊橋技科大),浅野孝夫, 今井桂子, 亀田貴之, 堂免俊 介(中央大学),塩出省吾, 毛利進太郎(神戸学院大),塩浦昭義(上智大), 伊藤美 保, 井上雅史, 工藤崇徳(東京理科大),土村展之(ログオプト),今井浩, 定兼邦 彦, 竹内史比古, 徳永裕己, 石関隆幸, 長井歩, 浅野泰仁(東京大学)

プログラム：

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$個が配置されている時（但し任意の３点 は同一直線上に無いとする）, 互いに重ならない$p$個の凸領域が存在し, 各領域は丁度赤点$n$個, 白点$m$個を含む様にできる」という2次元ハムサ ンドイッチ定理の一般化の証明について発表された．

16:00-17:00 藤沢克樹 (京都大学) 『SDPA(半正定値計画問題に対するソフトウェア)と大規模広域計算システム Ninf』

発表では, SDPA の設計思想や実装方法に触れると共に, SDPA や LPソフト ウェアを用いた新しい大域的最適化手法の広域計算システム Ninf への適 用, Ninf 専用の SDPA の開発, 及びインターネットを通じたこれらのシス テムの利用方法について述べられた.

日時: 平成１１年６月２４日（木）５時３０分〜６時３０分

場所: 東京大学 理学７号館 ２０２会議室

参加者(敬称略): 伊藤大雄, 茨木俊秀, 今井浩, 久保幹雄, 斎藤誠慈, 定兼邦彦, 土村展之, 藤澤克樹, 藤重悟, 室田一雄, 柳浦睦憲

10月の全体会議におい ては，A01班より次の6件の企画を提出した．

1. 品野勇治(東京農工大)，藤江哲也(神戸商大)：PUBBによるPCクラスタ環境にお ける並列分枝限定法
2. 今井浩，関根京子(東京大学)：グラフのTutte多項式計算システム
3. 伊藤大雄(豊橋技術科学大学)：二次元ハムサンドイッチ定理の一般化とその周辺
4. 徳永裕己，今井浩(東京大学)：量子計算機シミュレーションシステム
5. 野々部宏司(京都大学)：資源制約付きスケジューリング問題の定式化と近似解法
6. S. Iwata, L. Fleischer, S. Fujishige (大阪大学): A strongly polynomial-time algorithm for minimizing submodular functions

A01班平成11年度第2回班会議を，同年度第1回全体会議の際に合わせて

• 日時：平成11年10月28日(金) 11:40-13:10
• 場所：A01班 数理解析研究所206号室

• 日時: 12月22日(水)
• 場所: 大阪大学

２．A02班の活動状況

戸田先生の研究分担者に蓮沼徹先生が加わった． また，浅野の研究分担者に，築山修治先生（中央大），松井知己先生（東大）， 宇野毅明先生（東工大）が加わった． 研究を円滑に遂行するため以下の班会議を行った．

平成11年度特定領域研究(B)「アルゴリズム工学」A02班第1回会議

出席者: 15名(＋学生11人)(浅野孝夫，上原隆平，宇野毅明，草刈良至，周暁，田村明久，陳致中，永持仁，蓮沼徹，平田富夫，藤戸敏弘，夜久竹夫，渡辺治，小野孝男)

日時・場所: 平成11年5月25日，午前10時ー午後5時，中央大学1号館1205会議室

内容: 最近の研究に関し，1.-6.の報告及び討論が行われた．

1. 最小k分割カット問題について　　永持 仁(京都大学)
2. Test Instance Generators for SAT (and MAXSAT) 渡辺 治（発表），内田 智也，元木 光雄 (東工大)
3. Finding Double Euler Trails of Planar Graphs in Linear Time 陳致中(東京電機大学), Xin He (State University of New York at Buffalo)
4. A New Approach for Speeding Up Enumeration Algorithms~ 宇野 毅明（東工大）
5. コスト彩色問題に関する研究~ 周 暁（東北大）
6. アルゴリズム工学についての討論

平成11年度特定領域研究(B)「アルゴリズム工学」A02班第2回会議

出席者: 9名(浅野孝夫，宇野毅明，加藤直樹，草刈良至，谷聖一，永持仁， 　　　　平田富夫，藤戸敏弘，松井知己)

日時：1999年 9月1日（水）13:30-18:00

会場：北海道大学工学部A棟 A166

内容:

1. 最近の研究成果について以下の3件の講演が行われた．研究内容について活発な討論を行った．
   1. スポーツスケジューリング問題 　　松井知己（東大）
   2. 平面グラフで非交差なスタイナ林を求めるアルゴリズム 　　草苅良至（東北大）
   3. 絡み目のJones多項式の最高次数の計算につ? 　　谷 聖一（日大）
2. A02班アルゴリズムデータベースの構築に向けて

３．A03班活動状況

Ａ０３班の目的は，幾何に関係する諸問題の効率的解決法の開発に ある．直接的に幾何データを取り扱う問題だけではなく，入力は幾何に 関係がなくても，解決の手段として幾何的な取り扱いが有効である場合も あり，その守備範囲は広範である．そのためにともすると個別研究の集まり となってしまってアルゴリズム工学の趣旨に反することにもなりかねないので， 定期的に会合を開いて共通の方向を模索している．この目的のためにも共通の 基盤作りが不可欠であるが，Ａ０３班ではアルゴリズムの記述に適したＬＥＤＡ に焦点を当て，できる限りＬＥＤＡでアルゴリズムを記述して，まずはグループ 内でのソフト共有化を図ろうとしている．現在，そのための準備を進めており， １０月の京都における研究集会までには，アルゴリズムデータベースの一部と して公開する予定である．

第３回会合

平成１１年６月３，４日（木，金曜日）３日午後１時〜４日午後５時

場所：石川県文教会館（金沢市尾山町10-5）

参加者：浅野（哲夫），杉原厚吉，徳山豪，加藤直樹，今井桂子， 中野眞一，小保方幸二，山崎浩一，その他学生２名

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

４．A04班の活動状況

４．１．A04班 第3回 班会議 議事録(抜粋)

日時：平成 11 年 6 月 18 日（金） 16:30 〜 17:15

場所：奈良先端科学技術大学院大学附属図書館・マルチメディア提示室（３階）

出席者：15 名

議題 アルゴリズムのデータベース化 PVM（文中, 敬称略）

1. 各研究グループの進捗状況が報告された.
2. 全体としての問題点
   大学間を結んで PVM を実行するには, セキュリティの問題, データ転送の少ない課題の選択などがある.
3. PVM で解く課題について
   各研究グループで作成したプログラム（課題）をメーリングリストで 知らせる. 課題は複数の研究グループで重なっても構わない.
4. PVM のリーダー
   データベース化（公開）に向けて, ドキュメント, インターフェース などを統一する必要がある. そのため, 雛形を作成して戴くために, 藤原と朝廣にリーダーをお願いした.
5. URL
   アルゴリズムデータベースの URL のリンク集に, PVM の URL \\ http://www.epm.ornl.gov/pvm/pvm\_home.html を加えることが了承された. また, メーリングリストに流れた有用な情報をドキュメントとして, URL に置く.

日時：平成 11 年 9 月 3 日（金） 16:10 〜 18:00

場所：北海道大学知識メディア・ラボラトリー（ＶＢＬ） ２階コラボレーションルーム

出席者：16 名

講演

1. "Secure and Reliable Multi-Party Computation over NetWorks"
   Yasuaki Nishitani and Yoshihide Igarashi
   Department of Computer Science, Gunma University
2. "Optimal Fault-Tolerant Routings on Surviving Route Graph Model"
   Koichi Wada
   Department of Electrical and Computer Engineering,
   Nagoya Institute of Technology
   

審議事項（文中, 敬称略）

1. 沖縄（琉球大学）での班会議の中止について
   スケジュール過密のため, 1 月に沖縄にて行う予定の班会議を 中止することが決まった.
2. PVM について
   1. 陳から「PVM を用いた行列積の計算」について報告がなされた.
   2. 朝廣から「PVM を用いて組み合わせ問題を解くためのシステム （試作版）」の報告がされた.
3. ドキュメント, インターフェースの雛形の作成について
   雛形の作成を 10 月末をめどにリーダーの藤原と朝廣にお願いした.

A02班「グラフアルゴリズム」の紹介

A02班の研究対象は離散最適化問題の中でも 基礎的で特殊な構造をもつグラフ・ネットワーク問題と情報科学の基礎理論で総括的な 立場にある問題SAT（充足可能性問題）である. グラフ・ネットワークのアルゴリズム的に有効な構造的性質の発見と それを利用した高速アルゴリズムの提案およびその限界の究明が目標である． 効率的アルゴリズムが存在しない(より厳密には存在しないだろうと確信されている) NP困難な問題に対しては，精度の保証された近似解，すなわち，高品質の解， を求める高性能アルゴリズムの研究も含まれる． A02班の研究は，他の班の研究の基礎的な部分を構成していることも 多いので，グループ内の研究者間はもちろん， 他の班の研究者との情報交換も行ないながら，目標達成に向けて研究を遂行している．

以下にA02班の6人の研究代表者とその研究分担者の研究について紹介する．

ネットワークフローと半正定値計画法に基づく高性能近似アルゴリズムの研究

研究代表者：

浅野孝夫 (中央大学理工学部情報工学科)

研究分担者：

築山修治 (中央大学理工学部情報工学科)

松井知己（東京大学大学院工学研究科）

宇野毅明（東京工業大学大学院社会理工学研究科）

Widthを制限した場合のグラフ理論的計算問題の計算量解析

研究代表者：

戸田誠之助 (日本大学文理学部)

研究分担者：

夜久竹夫 (日本大学文理学部)

黒田耕嗣 (日本大学文理学部)

斉藤 明 (日本大学文理学部)

渡辺 治（東京工業大学大学院情報理工学研究科）

陳 致中（東京電機大学理工学部）

谷 聖一 (日本大学文理学部)

上原隆平(駒沢大学自然科学教室)

蓮沼 徹 (電気通信大学情報工学科)

• 画像データの情報処理に対するグラフアルゴリズムと 関連性の深い課題に関する研究．特に，地図情報をデータ ベース化する際に発生する地図情報の構造認識に関する研究と幾何的 な属性を備えていない情報構造（例えば，プログラムフローなど）の 視覚化に関する研究．
• 到達可能性判定問題を解くための省メモリ型アルゴリズムに 関する研究．
• グラフ同型性判定問題ならびにグラフ同型写像の個数を 求める問題に関するアルゴリズムの設計と解析．
• 最大点誘導部分グラフ抽出問題のアルゴリズムに関する研究．
• 最短路問題ならびに最小重み巡回ツアーを発見する問題の 近似アルゴリズムに関する研究．
• k-Chordalグラフの認識問題のアルゴリズムに関する研究．
• グラフのハミルトン性に関する研究．
• MAXSATの例題生成アルゴリズムに関する研究．

研究代表者: 永持 仁(京都大学大学院情報学研究科)

研究内容：本研究では, 基本的なグラフ・ネットワーク問題, とくに 連結度, カットに関連する問題を解く効率の良いアルゴリズムの開発を 行う. 最近では, Nagamochi-Ibarakiの最小カットアルゴリズムを 集合関数の最小化の視点でとらえ, その性質を用いて, 辺連結度増大問題にある種の付加制約を課しても効率よく解ける ことを示した. 例えば, 辺連結度を指定された値に上げるために 付加すべき辺数, および付加辺に接続する節点数をともに 最小にする問題を効率よく解くことができる. また, 連結度増大問題に関しては, 辺連結度と点連結度を 同時に増大させる問題に対しても種々のアルゴリズムを提案している. $(k-1)$-点連結グラフの点連結度を１増大させる問題は絶対誤差 $k/2$で解けることが知られているが, $(k-1)$-点連結グラフを $k$-点連結かつ$\ell$-辺連結なグラフにする問題は絶対誤差 $\max\{\ell+1,2k-4\}$で解けることを示した. さらに, 重みつき無向グラフを$k$個の節点集合に分割するために 除くべき辺集合（＝$k$-カット）の最小化問題に対しても, 2-カットの列挙に基づいた方法により, $k\leq 6$の場合, 従来の計算量を改善した.

組合せ問題の高性能近似アルゴリズムに関する研究

研究代表者：

平田富夫（名古屋大学工学研究科）

研究分担者：

藤戸敏弘（名古屋大学工学研究科）

小野孝男（名古屋大学工学研究科）

磯 直行 （中京大学情報科学部）

ネットワーク最適化問題の解法効率化に関する研究

研究代表者：渡邉敏正 (広島大学工学部)

研究内容：主に以下の３つの方向で研究を進めている． (1) グラフの辺付加問題の解法；(2) ペトリネットアルゴリズムの設計と解析； (3) プリント基板，VLSIのレイアウト設計における最適化手法．

(1)では，与えられたグラフにコスト総和最小の辺集合を付加することにより 所望の点連結度や辺連結度を達成する問題に対し，そのような辺集合を求める 手法を設計する．このとき，グラフの指定された点部分集合内の点間に所望の連 結度を得る問題が，耐故障ネットワーク設計等への応用上有用である．ここでの 成果の一つは，指定点集合に対する３点連結化のための線形時間アルゴリズムを 与えたことである． (2)では，離散事象のモデル化に有用なペトリネットに関して，次の(a)〜(c) に取り組んでいる：(a) サイフォン抽出法，(b) 発火系列問題の解法，(c) インバリアント計算法の高速化． (a)では，指定したプレース集合を含むようなサイフォンの効率的抽出法の設計 に取り組んでおり，これは(b)や(c)に有用である．既に高速な抽出法は提案 している．(b)については，制限されたクラスに対する効率的解法の設計，およ び，サイフォンに着目して，一般的なクラスに対する高速で精度の高い発見的解法 を与えている．(c)のインバリアントはモデルの解析，検証に有用であるが， 効率的な計算法が望まれている．サイフォンに注目することにより，非常 に高速な計算法を与えたことが一つの成果であり，さらに改良を進めている． (3)では，主に次の(a),(b)に取り組んでいる：(a) プリント基板の層数最小設 計法；(b)多層配線問題におけるビア数最小化手法．(a)は基本的には平面グラフ 抽出問題とグラフの交差数最小描画問題であるが，（これまで取り組みのなかっ た）反転できない部分グラフを持つ場合の平面抽出法に対する解法を与えている ことが成果である．(b)については３層あるいは４層配線におけるビア数最小化 に関する精度の高い発見的解法を提案している．

スケジューリングのグラフアルゴリズムによる解法

研究代表者：周 暁 (東北大学大学院情報科学研究科)
研究分担者：草苅 良至 (東北大学大学院情報科学研究科)

研究内容：彩色問題はスケジューリング問題によく応用されることが知られてい る．本研究では部分 $k$-木に対して全彩色問題を解く線形時間 アルゴリズムの開発を行なう．グラフ $G$ の全彩色とは $G$ の 全ての点と辺をどの隣接する2点, どの隣接する2辺, どの1点と それに接続する辺も全て異なる色になるように彩色することである. 与えられた部分 $k$-木の最小色数を用いた全彩色を求める 線形時間アルゴリズムは今まで知られていなかった. 私たちは そのような最初の線形時間アルゴリズムを与えた．この成果を国際会 議ISAAC'99で発表する予定である． また平面グラフの非交差スタイナ林に関する研究も行っている. $G=(V,E)$を各辺に非負の重みが付いている平面グラフとし， ${\cal N}=\{N_1,N_2,\cdots,N_k \}$を $V$の部分集合(ネット)からなる族とする． このとき，各ネットをそれぞれ連結する$k$本の木の集合 ${\cal T}=\{T_1,T_2,\cdots,T_k\}$で 互いに非交差で重みの総和が最小な林を 非交差スタイナ林と呼ぶ． 本研究では, 自然な制約のもとで, 非交差スタイナ林を求めるアルゴリズムの開発を行なう.

図１：The First Japanese Hungarian Symposium on Discrete Mathematics and Its Applicationsの参加者 (1999年3月19日於京大会館前)

6月の終りから7月にかけて，計算複雑さの理論の研究で有名な，Avi Wigderson，Ran Raz，Maria Bonnetの3氏が本特定研究の援助によって来日し た．そこで，京都大学情報学研究科に客員教授として滞在中の Magnus Halldorsson氏にも加わっていただき，7月2日（金）に京都大学においてセミ ナーを開催した．当日の演題とアブストラクトに関しては添付のプログラムを 参照されたい．

なお，3氏はこれより先，西野哲朗先生が開催された電気通信大学での セミナーにも講師として招かれており，いずれのセミナーも多くの聴衆を集め て非常に好評であった．なお，今回の3氏の来日に当たっては広島市立大学の 新井紀子先生の大きな御尽力を頂いた．

Kyoto Seminar on Theoretical Computer Science

July 2 (Fri), 1999

Seminar Room, 2nd Floor Venture Business Laboratory Kyoto University Sakyo, Kyoto 606-01 (For location, see www.vbl.kyoto-u.ac.jp/About/location/index-j.html)
Contact: Prof. Kazuo Iwama (075-UUU-YYYY, iwama＠XXXX.kyoto-u.ac.jp)

Professor Avi Wigderson

11:00-12:00 Short Proofs are Narrow -- Resolution made Simple ,Avi Wigderson (The Hebrew University, Jerusalem, and The Institute for Advanced Study, Princeton)
The width of a Resolution proof is defined to be the maximal number of literals in any clause of the proof. In this paper we relate proof width to proof length (=size), in both general Resolution, and its tree-like variant. The following consequences of these relations reveal width as a crucial ``resource'' of Resolution proofs.
In one direction, the relations allow us to give simple, unified proofs of almost all known exponential lower bounds on size of resolution proofs, as well as several interesting new ones. They all follow from width lower bounds, and we show how these follow from natural expansion property of clauses of the input tautology.
In the other direction, the width-size relations naturally suggest a simple dynamic programming procedure for automated theorem proving - one which simply searches for small width proofs. This relation guarantees that the running time (and thus the size of the produced proof) is at most quasi-polynomial in the smallest tree-like proof. The new algorithm is never much worse than any of the recursive automated provers (such as DLL) used in practice. In contrast, we present a family of tautologies on which it is exponentially faster.
The lower bound part of this gap is proved using a new general connection between the pebbling number of any graph and the tree-like proof size of a related tautology. A byproduct is an exponential gap between the power of general and tree-like Resolution.
Joint work with Eli Ben Sasson

12:00 -- 13:30 Lunch

Professor Maria Luisa Bonet

13:30 -- 14:30 Comparison of Proof Search Algorithms for Resolution and Polynomial Calculus, Maria Luisa Bonet (Cataluna Polytechnic University)
This talk is concerned with the complexity of proofs and of searching for proofs in two propositional proof system: Resolution and Polynomial Calculus ($PC$). For the former system we show that the recently proposed algorithm of Ben-Sasoon and Widgerson for searching for proofs cannot give better than weakly exponential performance. This is a consequence of showing optimality of their general relationship refered to as size-width trade-off. We moreover obtain the optimality of the size-width trade-off for the widely used restrictions of resolution: Regular, Davis-Putnam, Negative, Positive and Linear. As for the second system, we show that the translation to polynomials of a $CNF$ formula having short resolution proofs, cannot be refuted in polynomial calculus with degree less than $\Omega(\log n)$. A consequence of this is that the simulation of resolution by $PC$ %of \cite{cei} cannot be improved to better than quasipolynomial in the case we start with small resolution proofs. We conjecture that the simulation of Cleg-Edmonds-Impagliazzo is optimal.

Professor Ran Raz

14:45--15:45 Separation of the Monotone NC Hierarchy, Ran Raz (Weizmann Institute)
We prove tight lower bounds, of up to $n^{\epsilon}$, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1) monotone-NC $\neq$ monotone-P. 2) $\forall i \geq 1$, monotone-$NC^i$ $\neq$ monotone-$NC^{i+1}$. 3) More generally: For any integer function $D(n)$, up to $n^{\epsilon}$ (for some $\epsilon > 0$), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth $D(n)$, but that cannot be computed by {\bf any} (fan-in 2) monotone Boolean circuits of depth less than $Const \cdot D(n)$ (for some constant $Const$).
Only a separation of monotone-$NC^1$ from monotone-$NC^{2}$ was previously known.
Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1) For $st$-connectivity, we get a tight lower bound of $\Omega(\log^2n)$. That is, we get a new proof for Karchmer-Wigderson's theorem, as an immediate corollary of our general result. 2) For the $k$-clique function, with $k \leq n^{\epsilon}$, we get a tight lower bound of $\Omega(k \log n)$. Only a bound of $\Omega(k)$ was previously known.

Professor Magnus M Halldorsson

16:00-17:00 Scheduling Dependent Jobs and Graph Multicoloring Problems, Magnus M Halldorsson (University of Iceland and Kyoto University)
In multiprocessor systems certain resources may not be shared concurrently by some sets of jobs. Scheduling dependent jobs on multiple machines is modeled by the graph multi-coloring problem, where each node (job) is to be assigned a set of colors (time units). Schedules (colorings) can be either non-preemptive, when vertices are assigned contiguous sets of colors, or preemptive.
We survey recent results on multicoloring various classes of graphs. While much work has traditionally been done on the makespan measure (the number of colors used), much less has been done regarding to the sum-of-completion times measure. The latter gives rise to the *sum multicoloring* problem.
Some of the particular results discussed include:

• An approximation-preserving reduction of the sum multicoloring problem to finding (approximately) maximum independent sets in the given graph,
• Exact algorithms for various multicoloring problems on trees,
• Polynomial time approximation schemes for multicoloring problems on partial k-trees and planar graphs.

This is joint work with several sets of researchers, most prominently Amotz Bar-Noy, Guy Kortsarz, and Hadas Shachnai.

今井 浩 (東京大学大学院理学系研究科)

Computing and Combinatorics Conference, 略してCOCOONの第5回会議が7月26 日から28日の期間，中央大学駿河台記念館で開催された．この会議は，今では アジア・オセアニア地域の冬の恒例の国際会議となったISAAC (International Symposium on Algorithms and Computation)の兄弟的な会議といえるところま で成長してきた．ISAACのシリーズの第1回は，International SIGAL Symposiumということで情報処理学会アルゴリズム研究会(SIGAL)を母体に1990 年夏に開催された．その点，まさしく現在のこの特定研究アルゴリズム工学に 関わられている先生方を始めとしたご努力で，まさしく日本で生まれた国際会 議である．ISAACシリーズの第1回は夏開催だったが，翌年のSymposium on Algorithmsが台湾で開催ということで，「台湾の夏は暑い」とかの理由で冬に 開催され，以降冬が寒すぎる北京では夏の開催などと季節が開催場所で変わっ ていたのが，90年代中頃からISAACシリーズは冬の会議として定着した(もっと もオーストラリアでは夏になるわけだが)．
そのような状況のところに，1995年夏にDing-Zhu Du, Ming Liの北米で活躍さ れている中国系の先生の旗振りで，北京で産声を上げたのがこのCOCOON会議シ リーズの始まりである．以降，COCOONの方は1996年香港，1997年上海，1998年 台北と夏に開催され，この第5回で初めて中国語圏の外に出たことになる．会 議名称はComputing and Combinatoricsということで，ISAACの「アルゴリズム と計算」より「組合せ論」の方に重点をおいていると言える．また，これは人 によるかもしれないが，このComputingに計算量の意味付けをする傾向もある． 組合せ論自体は非常に幅広い分野であるが，第2回のCOCOONの頃から計算に関 連した組合せ論ということで論文募集がされるようになっている．
夏の時期には，伝統的なICALPの他にもさまざまな国際会議が開催されており， たとえばEuropean Symposium on Algorithmsは従来の9月開催から今年は始め て7月開催となった．その意味で，厳しい国際会議間の争いともいえる中で， 本年のCOCOON'99会議は開催された．主催は本特定領域研究「アルゴリズム工 学」と中央大学であり，情報処理学会アルゴリズム研究会と電子情報通信学会 コンピュテーション研究会の後援を得た．中央大学浅野孝夫先生と私が会議委 員長，当時日本IBM・現在東北大学の徳山豪先生とD. T. Lee先生がプログラム 委員長，群馬大学の中野眞一先生が広報，そして日本からはさらに東京大学宮 野悟先生，東京電機大学陳致中先生がプログラム委員をされた．論文募集に対 し88件の投稿があり，その中から46件の論文が選ばれた．採択率という点では 比較的高めであるが，レベルは通常の年以上のものになっており，これもプロ グラム委員会のご努力の賜物である．
会議の招待講演者としてIBM Almaden研究所のPrabharkar Raghavan博士と，日 本から日本大学戸田誠之助先生が講演をされた．Raghavan博士はWebのリンク 構造をグラフとしてモデル化するという，まさしく理論によって今応用の最先 端のWebを解析するという講演を，戸田先生はグラフ上での到達可能性の問題 に関する計算量の問題について最新の成果を講演された．また，COCOON'99の 特別セッションとして，アルゴリズム工学に関連の深いアルゴリズムデータベー スに直結したシステムLEDAを開発したKurt Mehlhorn教授のLEDA特別講演も開 催された．Mehlhorn教授はCOCOON'99のプログラム委員もされていたが，なに よりも北陸先端大学浅野哲夫先生のご尽力でこの講演が実現した．
このような招待講演・特別講演と通常の46件のレベルの高い講演からなるプロ グラムで，開催の場所が東京の中心のお茶の水ということで，150名以上の参 加者からなる盛況な会議となった．これに，Mehlhorn教授のLEDA特別講演は公 開講演とし，その際にはさらにプラス20名の参加となった．会議録は， Springer-VerlagよりLecture Notes in Computer Scienceのシリーズで出版さ れた．
このように盛況な会議になったのも，招待講演者招聘などで特定研究アルゴリ ズム工学の方から多大なご援助を頂き，中央大学の方から浅野孝夫先生 のご尽力で中央大学主催ということで会場費・会議運営費・懇親会費について 多大な援助も頂き，それによって一般の登録費をおさえることができるととも に，学生の登録費をほぼ会議録費相当くらいの非常に低額に抑えられたという ことが大いに影響している．そのような中でCOCOON恒例の遠足では浅草・屋形 船を満喫でき，懇親会も中央大学を代表して理工学研究所長の伊理正夫先生に ご挨拶頂き，後半では琴の演奏も行われるという賑やかなものとなった．また， 学生登録費は安いとはいっても何かと物いりな東京まで学生さんを多数参加さ せて下さったアルゴリズム工学関係の諸先生のご配慮もありがたいものであっ た．もちろん会議においてはアルゴリズム工学の成果の発表が多数発表され， また参加した外国人研究者もその後日本の各大学を訪問するなどして交流を図っ ていた．個人的には今回のCOCOONが初めて中国語圏の外で開催され，このよう にレベルの高い盛況なものとなったことで，COCOONシリーズの会議が真にアジ ア・オセアニア地域での夏の計算と組合せ論に関する会議として認知されるこ とに大いに貢献したと思っている．
このようにCOCOON'99を本当に成功裏に終了することができたのは，アルゴリ ズム工学からの全面的なご協力をえて中央大学と共同で主催して開催して頂い たからこそで，ここにアルゴリズム工学の皆様に感謝申し上げます．来年の COCOONは，オーストラリアのシドニーで夏に開催される予定で，オリンピック の前にアジア・オセアニア地域でのアルゴリズム工学の成果の競演となること と思いますので，再び皆様からの熱烈な支持をもって南半球に飛んで頂ければ と存じます．

７月２６日から３日間の会期で計算の理論と組み合わせ理論に関する 第５回の国際会議COCOON (International Computing and Combinatorics Conference)が中央大学駿河台記念ホールにおいて開催されるのを 期に，講演を含めて世界的な見地から本研究グループの活動について 意見を求めるために，アルゴリズムの分野で世界的に著名なドイツ マックスプランク研究所の所長であるDr. Kurt Mehlhornを本科学研究費 にて日本に招請した．
Mehlhorn博士は，ヨーロッパを代表する理論計算機科学者であり，これまでに グラフアルゴリズムと計算幾何学の分野において理論面で優れた業績を多数 発表してきているが，決して理論のための理論の研究になっていない所が 彼の哲学を反映していると言えよう．彼は米国でPh.Dを取得後直ちにドイツの ザールランド大学教授に２６歳の若さで抜擢され，同大学での計算機科学の 教育研究を一任されたが，彼が最初に取り組んだのは，抽象的なアルゴリズムの 記述と具体的なプログラムとの差を縮めることであった．そのために開発 されたのが，LEDA (Library for Efficient Data Types and Algorithms) である．ライブラリという名前の通り，多数のアルゴリズムをライブラリとして 含んではいるが，その最大の目的は抽象度の高いアルゴリズム記述言語の 開発にあった．つまり，テキストに擬似言語で記述されたアルゴリズムを そのままの形で実装できるようにすることであった．このプロジェクトは 約１０年前に正式にスタートし，今日までその守備範囲を着実に拡大してきて いる．
今回，Mehlhorn博士を日本に招請したのは，本特定研究グループの研究課題 である「アルゴリズム工学」の立場から求められているアルゴリズムの実際的な 実行と活用にLEDAが必須ツールとしての役割を果たすことができるのでは ないかということで，同様の立場で長年の経験がある同博士から貴重な意見を 拝聴したいという考えがあったからである．
COCOONでの研究発表は７月２８日の午前中にすべて終了したが，同日午後の 特別セッションでMehlhorn博士よりLEDAを紹介する講演があった．同博士は 所長という地位にありながら，今でもLEDAに関してはソースレベルで貢献して いるというだけあって，実演を交えながらLEDAのシステムや使い勝手について 熱演が続いた．今回はアルゴリズムの専門家が対象としうこともあって， LEDAのシステムについてかなり詳細な説明もあったが，複雑なアルゴリズムが 如何にも簡単に実行される様子は聴衆を魅了したようである．誤差なしの 計算がサポートされている点もLEDAの特徴の一つであるが，$a + \sqrt{b}$の ような形式の数値でも誤差なし計算ができることを知ったのは個人的に大きな 収穫であった．実際，COCOON自体はかなり理論面に偏った国際会議であるが， その会議の聴衆が２時間以上に及んだ彼の講演に熱心に聞き入っていたこと からも分かるように，今回の講演は話者の哲学と熱意が直接的に聴衆に伝わって 来る，迫力のあるものであった．講演後，Mehlhorn博士も自らの講演としても 生涯で最高の部類に入るものだったと言っていたが，報告者にとっても 今までに聞いた招待講演では文句なく最高のものであった．
最後に，Mehlhorn博士は，東京での講演の後は北陸先端大学院大学と京都大学 でも（それぞれ別々の）講演をされたことを付記しておく．

1999年の5月10日から15日まで, Sixth SIAM Conference on Optimization (5/10〜12) 及び 1999 SIAM Annual Meeting (5/12〜15) がアメリカ合衆国ジョージア州アトランタのシェラトンアトランタホテルにて 行われた. SIAM では, Annual Meeting とその他の会議を併せて実施するという試みを 昨年から行っており, 昨年は Conference on Discrete Mathematics と連続で 開催されていた. 以下, 私の聞いた発表を中心に紹介する.
Conference on Optimization では, 会議に対応する論文誌の内容から推測できる通り, 内点法に関する発表が半分近くを占めていた. 但し, その内容は多岐にわたっており, 様々な分野の研究者が「内点法」という同じ土俵の上で戦っている, という感じであろうか. ここ数年, 半正定値計画(semidefinite programming, 略してSDP) に対する内点法の研究が中心となっているが, 今回の会議では, SDPだけでなく 2次錐計画 (second-order cone programming) などの, いわゆる錐計画 (cone programming) に関する話が幾つか見受けられた. 錐計画は, 内点法の中で特に成功を納めている主双対内点法が うまく働く枠組みとして, 最近注目を集めており, 理論的な興味及び多彩な応用から, 今後も盛んに研究されそうである.
また, 第2回 SIAM Activity Group on Optimization Prize が Michel X. Goemans と David P. Williamson の論文 [1] に対して送られ, その受賞記念講演として, Williamson による発表があった [2]. Williamson の発表を他の会議で聞かれた方も多いと思われるが, 今回もまた, とても分かりやすい発表であった. 講演の最後では, 論文 [1] に引き続き 様々な研究者により発表された論文のリストが示された. いずれの論文も素晴らしい内容なのだが, それらの出発地点となった Goemans--Williamson の結果がどれだけ斬新かつ優れたものであるかを 改めて思い知らされた.
Conference では, 上記の Williamson の記念講演の他にも SDP緩和に関する発表が数件あったが, それらの発表者に共通する認識は, 「SDP緩和はもはや高価な道具ではなく, これまでのLP緩和に取って代わる存在になる」, というものであった. このような話を聞くと, 組合せ最適化や整数計画の分野の研究者にとって, これまでのLPと同様に SDPも常識として知っておくべき事項なのかも知れない, と考えさせられた.
その他, Olvi L. Mangasarian による招待講演では, データマイニングの様々な問題が線形または非線形計画の問題として解ける, という内容であり, 非常に興味深かった [3].
Annual Meeting のセッションの内容は応用数学の様々な分野に渡り, 私の知らない分野の発表が殆んどであったが, 幾つかの発表に顔を出してみた. 中でも興味深かったのは ``Graph algorithms applied to material theory'' というセッションであった [4]. 最短路問題, 最大流問題などのネットワーク最適化の手法が, 統計物理学のとある分野において, 最近盛んに用いられているとのことで, 組合せ最適化と統計物理学の関係について数人が発表してくれたのだが, 難しい物理の用語の羅列で内容的には殆んど理解できなかった. しかし, 組合せ最適化がこれまで(私の知る限り)無関係と思われていた分野で 役に立っていると知り, 組合せ最適化の研究者として, 何となく嬉しくなってしまった.
上記で紹介した発表に興味をお持ちの方は, 下記の URL [2] -- [4] を参照して頂きたい.