電子情報通信学会総合大会講演要旨
D-1-10
施設配置問題に対するMYZアルゴリズムの分散化
○楠見僚也・山田敏規(埼玉大)
施設配置問題とは,携帯電話の基地局や学校などの設立地計画をモデル化した問題である.この問題に対する近似解法の研究が進められており,さまざまな定数近似アルゴリズムが提案されている.しかし,これらの近似アルゴリズムはネットワーク全体を把握していることが前提条件となっており,無線センサのようなネットワークでは,全体の情報を収集・維持するのに膨大な時間と情報量が必要となってしまう.これらを解決するために,各ノードが持ちうる情報からネットワークを構成する分散アルゴリズムが考えられている.本稿では,定数近似アルゴリズムであるMYZアルゴリズムの概要とこれを分散化したアルゴリズムについて報告する.