伊藤大雄（豊橋技術科学大学）
INFORMS-FORMS Seoul 2000 ConferenceはInformation and Knowledge Management in the 21st Centuryというタイトルで2000年6月18-21日の4日間、韓国のソウル で開催されました。
INFORMSは毎年春と秋に会議を行ってきましたが、聞くところによると今後は秋の会 議を今回の様にKORMS等の他の学会と共催の国際会議にしていく計画だそうで、今回 はその第1回目になります。 会場はソウル市南部のCOEX国際会議場という所で、webの情報によると今年５月に完 成したばかりです。2つのホテル、それに展示場、巨大な地下街を備えた立派な施設 で、できたてでもあり、さすがに綺麗でした。
会議は、発表論文数約800件、408カ国から合計約870名の参加者があり、とても盛大 な会議でした。日本からも非常に多くの参加者があり、特定研のメンバーも当然沢山 参加していましたが、特に私の発表したセッションは、発表者が田村明久先生（京都 大学）と岩田覚先生（現東京大学）と私で、座長が増山繁先生（豊橋技科大）と、こ の特定研のメンバーで占めてしまいました。
印象に残った発表としては、UC BarkeleyのDorit Hochbaumによるチュートリアル講 演``A Framework for Half Integrality and 2-Approximations''がありました。多 くのNP困難な最適化問題に対し、半整数性に着目して近似解を算出する手法は、優秀 な才能による一つの思い付きが新しい有用で魅力的な世界を開く、という良い例でし た。 Unsan大学のKim Hyun-joonによる``Calculating Flow-based Network Survivability''は全対地間に要求量が設定されたフローネットワークにおいてk本 の枝故障で失われるフローの最悪量という視点でネットワーク耐力を評価していまし た。ただ、このk-edge-survivabilityは計算自体がNP困難になるので、上下限を評 価していましたが、せめて値を計算するぐらいは多項式時間でできる基準にした方が 良いかもしれません。
余談ですが、今回は大学時代に研究室に留学していた韓国人（今は社長）に連れられ て犬を食することができました。 香草と一緒に長時間煮てあるので、臭みは全く無く、ゼラチンが口内に心地よく、な かなかの美味と言えます。 ソウル五輪以後、韓国でも食べる人が少なくなってきたそうですが、自国の基準で他 国の文化を野蛮呼ばわりする無体な意見には耳を貸さずに、自国の文化を守って欲し いものです。
櫻井 幸一（九州大学大学院）
数論アルゴリズムシンポジム(Algorithmic Number Theory Symposium) (2000年7月2日〜7日) に出席した。場所は、オランダのライデン(Leiden)。 (http://www.math.leidenuniv.nl/~desmit/ants4/)
このシンポジム(ANTS)は、1994年にはじまり、今回で第４回目となる。 公開鍵暗号の発展を背景に、その要素技術である 数論アルゴリズムや計算論的代数の研究者が 集まったのがきっかけとなっている。
今回は、4件の招待講演と36件の研究論文とが発表され、 参加者は、世界から130名程度。 この4件の招待講演のうち3件が, Lattice reduction (格子還元)に関するものであり、 研究発表でも 格子還元アルゴリズムの改良や応用に 関するものが数件あった。
格子還元アルゴリズムは、LovaszやLestra兄弟が開発したが、 Shamirがナップサック暗号の解析に成功し、 暗号解読の基本技術の１つとなっている。 最近では、暗号の設計にも積極的に格子還元アルゴリズム が応用され、注目をあびている。
ハーバードの天才Noam D. Elkies (http://abel.math.harvard.edu/~elkies/) 格子還元アルゴリズムを用いての、代数曲線の有理点の 近似計算(Femart予想の一種の変型)を行なっていた。 彼が講演の際、板書した "From Euclid (algorithm) To Lovasz-Lestra-Lenstra (algorithm)" は、印象深い。
国内では、 格子還元アルゴリズムは暗号研究者にとっては 周知であるが、アルゴリズム研究者にとっては あまり知られていなく、数学者においてはこれを 知るものはほとんどいないのが現状である。 (異分野間の)研究者の交流と、 格子還元アルゴリズムの理論と応用との 発展を今後期待したい。
石井利昌 (豊橋技術科学大学)
7th Scandinavian Workshop on Algorithm Theory (SWAT 2000)は ノルウェーのベルゲンにおいて2000年7月5日から7日の日程で開催された. ベルゲンは, ノルウェーの中では緯度の低い方に位置するが, それでもこの時期は白夜に近くて夜の12時でもかなり明るく, 時間の 感覚がおかしくなりそうだった. 町は, 海に面したヨーロッパらしい きれいな町で, 気候の方も過ごしやすく, 夏なのに少々肌寒いくらいだった. 今回の会議では, 43件の一般講演と3件の招待講演があり, 参加者は100人弱くらいだった.
初日の招待講演では, M. Thorup氏が``Dynamic Graph Algorithms with Applications"という演題で, Connectivity や Minimum Spanning Tree といったいろいろなグラフの 情報を保持する Dynamic Graph Algorithmと, それを用いることによって 高速化された問題 について, 話されていた. かなり計算時間が改善されている例もあり, これまであまり意識しなかったが, Dynamic Algorithmの重要性を認識させられる講演だった. 特に, Graph Connectivityを保持する Dynamic Algorithm については, 自分の研究分野が Graph Connectivityであることもあり, 興味深いテーマだった. Dynamic Algorithmに関しては, 初日の他に 2日目にY. Dinitz氏が ``Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph''という題目で, 5-辺連結成分を保持するDynamic Algorithm について発表されていた. その他にも, R. Hassin氏の``Robust Matchings and Maximum Clustering'' など興味深い発表がいくつかあった.
藤田 聡（広島大学工学部） 牧野 和久（大阪大学大学院基礎工学研究科）
2000年7月26-28日の3日間, オーストラリア, シドニーのボンダイビーチにおいて, The Sixth Annual International Computing and Combinatorics Conference (COCOON 2000)が 開催された. 会議への総登録者数は76名で, うち14名がjpドメインからの参加者で あった. 日本からの参加者の多くは本特定領域研究の関係者の方々であり, 藤田，牧野も, この科研費から旅費の補助をいただいて参加した.
招待講演は Christos H. Papadimitriou 氏の “Theoretical Problems Related to the Internet”と Richard P. Brent 氏の “Recent Progress and Prospects for Integer Factorisation Algorithms”であっ た. Papadimitriou 氏の講演は, 「インターネットはなぜうまく動くのか」という素朴な問いかけから始まり, インターネット上に現れる様々な問題のモデル化やその理論的な評価について 最近の結果を交えて解説したものであり, 大変興味深かった. 今後このような研究が理論計算科学の分野で盛んになることを予感させる. いっぽう Brent 氏の講演では, 整数の因数分解アルゴリズムに関する 最新の成果について解説がなされた.
一般講演では, 81編の応募の中から採択された44編の発表があった. 講演で扱われたトピックスは，計算幾何，グラフ描画，グラフアルゴリズム， オンラインアルゴリズム，並列分散アルゴリズム，離散数学，組合せ最適化，データ 構造，量子計算などであった． COCOON'2000の論文賞（Hao Wang Award）は，この特定領域研究のメンバーである京 大の加藤直樹先生のグループの論文
Approximating Uniform Triangular Meshes in Polygons by F. Aurenhammer, N. Katoh, H. Kojima, M. Ohsaki and Y. Xu
が受賞した．この論文では, 多角形を“一様に”三角形分割する問題が取り扱われて いる. 論文では一様性の自然な評価基準として３種類の目的関数が導入され， そのそれぞれに対して精度が理論的に保証された近似アルゴリズムが提案されている. 理論的面白さに加え，建築分野への応用という点でも高く評価されるべき論文であろ う.
その他の一般講演でも, 近似アルゴリズム，オンラインアルゴリズムなどの分野に興 味を覚えた講演が 数多く存在した. 論文集はLNCS Vol.1858として出版されているので, 興味をお持ちの方はぜひ参照していただきたい.
来年の COCOON は, 中国の Guilin で8月 20 - 22日に開催される予定である．