pp280
福永拓郎
複雑なネットワーク設計問題に近似解を与える解析法とその適用例
所望の制約を満たすネットワークの中でできるだけ低コストのものを求めるネットワーク設計問題は，典型的なグラフ最適化問題の一つである．故障に強い通信ネットワークを構築するのに役立つだけではなく，計算機科学の多岐にわたる分野に応用を持つ．本稿では，ネットワーク設計問題に対する手法の一つであるスパイダ被覆アルゴリズムの基礎と最新の研究動向を紹介する．
小特集 グラフアルゴリズムの最先端 8. CAT(0)空間上のアルゴリズムと最適化について Algorithm and Optimization on CAT(0)-space
pp276
平井広志
距離空間によるモデリング，解法と最適化理論
CAT(0)空間と呼ばれるユークリッド空間や双曲空間を一般化した距離空間がある．CAT(0)とは，「曲率が非正」ということを意味している．この空間は，ユークリッド空間で成り立つ様々な良い性質を引き継いでいる．特に，任意の2点を結ぶ測地線（≃最短路）が一意に定まる．このことから凸関数なども自然に定義される．最近になって，CAT(0)空間を利用したモデリングやその上でのアルゴリズム・最適化理論が展開され始めている．本稿では，そのような試みの一端を紹介する．