文献

J-GLOBAL ID：202202262279486632   整理番号：22A0835361

確率最大化最短経路問題のための完全多項式時間近似スキーム【JST・京大機械翻訳】

A fully polynomial time approximation scheme for the probability maximizing shortest path problem

著者 (3件)： Lee Jisun (Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720, USA) ,  Joung Seulgi (Department of Industrial Engineering, Chonnam National University, 77, Yongbong-ro, Buk-gu, Gwangju 61186, Republic of Korea) ,  Lee Kyungsik (Department of Industrial Engineering, Seoul National University, 1 Gwanak-ro, Gwanak-gu, Seoul 08826, Republic of Korea)
資料名： European Journal of Operational Research  (European Journal of Operational Research)
巻： 300  号： 1  ページ： 35-45  発行年： 2022年 
JST資料番号： A0547A  ISSN： 0377-2217  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,最短経路問題の最大化確率を考察した。合理的な平均と標準偏差を有する独立正規ランダム変数である各アークの長さを有する与えられた有向グラフに対して,問題は,与えられた限界内で目的地に到着する確率を最大化する簡単なs-t経路を見つけることである。最初に,この問題は,整数に限定された各アークの長さの平均を有する有向非巡回グラフ上でさえNP困難であることを証明した。次に,多項式時間で解くことができる非自明な特殊ケースとともに,この問題に対する擬似多項式時間厳密アルゴリズムを示した。最後に,決定論的最短経路問題を反復的に解く完全多項式時間近似方式(FPTAS)を示した。提案した近似スキームの構造は,対応する決定論的問題が多項式可解であるならば,他の確率最大化組合せ最適化問題に対してFPTASを考案するために適用できる。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *多項式 ,  *最短路問題 ,  標準偏差 ,  有向グラフ ,  経路 ,  *近似法 ,  変数 ,  問題 ,  NP困難 ,  組合せ最適化問題
準シソーラス用語： ランダム変数 ,  *多項式時間 ,  組合せ最適化 ,  決定論 ,  *最短経路 , 【Automatic Indexing@JST】

著者キーワード (5件)： 組合せ最適化 ,  最短経路 ,  確率最大化 ,  正確なアルゴリズム ,  完全多項式時間近似スキーム

分類 (5件)： 数値計算  (JE02000J) ,  計算理論  (JB02000A) ,  数理計画法  (KA03030M) ,  計算機網  (JC03000K) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (4件)： 確率 ,  最大化 ,  最短経路問題 ,  完全多項式時間近似スキーム