組合せ最適化にもとづくネットワーク符号化アルゴリズムの研究

点击翻译按钮获取中文摘要

国際学術誌 “IEEE Transactions on Information Theory”に論文 “Multicasting in Linear Deterministic Relay Network by matrix completion”が採択された． 本研究は，無線通信ネットワークのモデルとしてAvestimhr, Diggavi, Tseにより提唱された “Linear Deterministic Relay Network (LDRN)” 上のマルチキャスト問題に対して，既存のYazdi, Savariによるアルゴリズムより高速なアルゴリズムを与えたものである．LDRNはネットワーク符号化の一部の符号化が固定されたネットワークとして捉えることもでき，近年組合せ最適化からも注目されているモデルである．提案したアルゴリズムの特筆すべき点として，全シンクに対するユニキャスト容量計算の現在最良の計算量と，漸近的に同じオーダーの計算量を達成している点が挙げられる．古典的な有線ネットワークにおいても，全シンクに対するユニキャスト容量計算より高速な決定性マルチキャストアルゴリズムは知られておらず，ある意味で予想される計算量の下界を達成しているとも言える．また，研究課題のネットワーク符号化と関連して，圧縮センシングに取り組み，新しい性能保証をもつアルゴリズムを与えた．本成果では，Lq最小化として知られていた非凸最適化問題を，二乗和多項式緩和を用いて多項式時間で解くアルゴリズムである．本アルゴリズムは，圧縮センシングに現れる非凸最適化問題が多項式時間で解けることを示した点で画期的であると評価され，理論計算機科学のトップ会議であるACM-SIAM Symposium on Discrete Algorithms (SODA 2016)に採択されている．