抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
コンパクトなルーティングのようなネットワーク設計問題において,目標は(近似)最短経路を用いてノード間のパケットを経路することである。これらのルートの望ましい特性は少数のホップであり,より信頼性が高く,伝送コストを低減する。アルゴリズム設計,Haeupler,Hershkowitz,およびZuzic(STOC’21)に対する確率的ツリー埋込みの圧倒的な成功に続いて,ホップ制約Ramsey型計量をツリーに埋め込む。特に,f:G(V,E)→Tの埋込みは,もしΔΨ_u→M,v→V,d_G(β.h)(u,v)≦d_T(u,v)≦t.d_G(h)(u,v)ならば,Ramseyホップ歪(t,M,β,h),(here t,β,h≧1およびM≡V)を有する。tは歪みと呼ばれ,βはホップ-延伸と呼ばれ,d_G(h)(u,v)は,ほとんどのhホップでu-v経路の最小重みを示す。Haeuplerらは,Mが頂点の1-ε画分とβ=t=O(frac{log{2}n})を含む埋込みを構築した。それらは,ホップ制約ネットワーク設計問題のための多重二基準近似アルゴリズムを得るためにそれらの埋込みを使用した。本論文では,まず,パラメータt=β=O(logn)/εを得るためのRamsey型埋込みを改善し,任意の歪パラメータt(Mのサイズを縮小するコスト)に一般化した。この埋込みは,Haeuplerらからのすべての近似アルゴリズムに対する多項式改良を直ちに意味し,ホップ制約付きclan埋込み(各頂点が複数のコピーを持つ)を構築し,それらをグループSteiner木問題のための二基準近似アルゴリズムを構築するために用いて,非制約バージョンの最先端をマッチングした。最後に,著者らの埋込み結果を用いてホップ制約距離オラクル,距離ラベリング,および最も顕著に,証明可能な保証を有する最初のホップ制約コンパクトルーティング方式を構築した。すべての計量データ構造は,非制約バージョンの最先端パラメータの状態にほとんど整合した。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
