|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
|
|
電子情報通信学会 - IEICE会誌 試し読みサイト
© Copyright IEICE. All rights reserved.
|
グラフアルゴリズムの最先端
小特集 9.
スパイダ被覆アルゴリズム
――ネットワーク設計の最新理論――
Spider Covering Algorithm: Recent Progress of Network Design
abstract
所望の制約を満たすネットワークの中でできるだけ低コストのものを求めるネットワーク設計問題は，典型的なグラフ最適化問題の一つである．故障に強い通信ネットワークを構築するのに役立つだけではなく，計算機科学の多岐にわたる分野に応用を持つ．本稿では，ネットワーク設計問題に対する手法の一つであるスパイダ被覆アルゴリズムの基礎と最新の研究動向を紹介する．
キーワード：組合せ最適化，ネットワーク設計，連結度，グラフアルゴリズム
私たちの周りには様々な種類のネットワークが存在する．中でも，通信ネットワークは今や生活に欠かせないインフラとなっている．通信ネットワークを故障に強くかつ低コストで運用するためには，その構成を工夫する必要がある．そのような要求を最適化問題としてモデル化したものがネットワーク設計問題であり，所望の制約を満たすネットワークの中でできるだけ低コストのものを求める組合せ最適化問題のことを指す．スタイナー木問題やスタイナーネットワーク問題など，極めて基礎的な最適化問題を多く含んでおり，その応用先は通信ネットワークの設計だけにとどまらず，データ解析や意思決定など計算機科学の多岐にわたる分野で見つけることができる(1)～(5)．
ほとんどのネットワーク設計問題はNP困難であるため，多項式時間で近似解を計算することが理論的に保証される近似アルゴリズムの研究が盛んに行われている．世界中の研究者が良い近似精度を達成するアルゴリズムの開発にしのぎを削っており，計算理論，数理最適化，離散数学などの分野で培われた数学的道具を駆使して，多くの巧妙な近似アルゴリズムがこれまで提案されている．ネットワーク設計問題に対する近似アルゴリズムの研究を通して得られた多くのアイデアはその後，その他の組合せ最適化問題に対するアルゴリズム開発でも欠かせないものとなっており，その意味でネットワーク設計問題は組合せ最適化の研究における中心的な役割を果たしていると言える．筆者の研究のモチベーションも，ネットワーク設計問題に対する近似アルゴリズムの研究を通して，様々な組合せ最適化問題に通用する普遍的なアイデアを見つけることにある．
続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。
電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。
電子情報通信学会 - IEICE会誌アプリをダウンロード
