文献

J-GLOBAL ID：201802290538816459   整理番号：18A0390560

多予算と重み付き有界度計量Steinerネットワーク問題【Powered by NICT】

The multi-budgeted and weighted bounded degree metric Steiner network problem

著者 (1件)： Stamoulis Georgios (Department of Data & Knowledge Engineering (DKE), Maastricht University, P.O. Box 616, 6200 MD, Maastricht, The Netherlands)
資料名： Journal of Parallel and Distributed Computing  (Journal of Parallel and Distributed Computing)
巻： 104  ページ： 36-48  発行年： 2017年 
JST資料番号： D0613B  ISSN： 0743-7315  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 計量サバイバルネットワーク設計問題(SND)(Jain,2001)のマルチ予算型版,Steinerネットワーク問題としても知られているを研究し,点の予め指定された対の間の通常の接続性要求(すなわち,数辺素経路の下限)に加えて,ここではまた,余分な線形制約(収支)のセットを満足するように依頼した。問題の自然なLP緩和の極値点解の組合せ特性と反復法を用いて,著者らは以下の性能保証を有する新しい近似アルゴリズムを設計:どの辺が高々f∈N収支に関与するならば,著者らは(f +2 , f +2)2基準近似アルゴリズムの多項式時間でできるかを示す,同じ因子により上から有界のポテンシャル予算オーバーフローによる最適化したものが最も(2 + f)時間でコストで解が得られる。換言すれば,近似と予算の破れは,収支中のすべてのエッジ間の最大周波数の線形関数である,収支自体の数の関数とは対照的に保証し,これは以前の手法よりも厳密な改善を構成する。提案アプローチが十分に柔軟で,それは,標準SND連結性制約を持つSND問題の最小重み付き有界度版(4 , 4)2基準アルゴリズムを提供するために使用できるか,および,さらにグラフの全ての頂点vに対しては実現可能な解におけるエッジへ入射する辺の重みの総和の上限であることが分かった。これらの問題,それらの明らかな理論的関心に加えて,光ネットワークシステムへのクラウドコンピューティングからの多数の実生活用途を持っている。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： グラフ ,  近似法 ,  連結性 ,  線形性 ,  逐次近似 ,  最適化 ,  アルゴリズム ,  *ネットワーク
準シソーラス用語： クラウドコンピューティング ,  光ネットワーク ,  線形関数 ,  多項式時間 ,  近似アルゴリズム ,  ネットワーク設計 ,  *有界 , 【Automatic Indexing@JST】

著者キーワード (5件)： サバイバルネットワーク設計 ,  アルゴリズムの設計と解析 ,  フォールトトレラント計算 ,  クラウドコンピューティング ,  通信ネットワーク

分類 (1件)： ディジタル計算機方式一般  (JC02010O)

タイトルに関連する用語 (3件)： 予算 ,  有界 ,  計量