抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
優先フレームワークにおけるDisjoint Path Allocation問題(DPA)を解析した。通信ネットワークにおける交通規制の問題に動機づけられて,DPAはグラフにおけるエッジ-ディスジョイント経路を割り当てる。DPAのためのオンラインアルゴリズムを過去に徹底的に研究したが,より強力なクラスの優先順位アルゴリズムを考慮することによって,この最適化問題の解析を拡大した。オンラインアルゴリズムのように,優先度アルゴリズムは,その入力を,その全体に入力する前に,連続的に入力のみを受け,個々の入力アイテムのために,不可解な決定を出力しなければならない。しかし,オンライン設定とは対照的に,優先度アルゴリズムは,すべての可能な入力アイテムのセットに関する順序を選択し,そして,実際の入力を,次に,この順序に従って提示した。優先度アルゴリズムは, greedy欲アルゴリズムの直感的に十分に理解できる概念のための自然モデルである。古典的優先設定の解析は別として,アドバイスを持つ優先順位アルゴリズムも考慮した。情報理論的観点からオンラインアルゴリズムを研究するのは,最近,アドバイスの概念を優先フレームワークに拡張した。本論文では,経路のグラフクラス上のDPA問題の古典的変形,長さ-Weighted DPAの関連する問題,および最終的にはツリーのグラフクラス上のDPAを解析した。著者らは,LWDPAにおける最適性に必要なアドバイスに関して,漸近的に整合する上限と下限を示し,ほとんどの3で最大値を持つツリーへの経路上のDPAに対する既知の最適性結果を一般化した。3より大きい最大度を有する樹木に関して,著者らは,アドバイスフリー優先設定における近似比率に関して,上界と下界のマッチングを証明した。最後に,そのようなツリーに対する最適性を達成するために必要なアドバイスに関する上限と下限を示した。【JST・京大機械翻訳】
