文献

J-GLOBAL ID：202102226212888918   整理番号：21A3306374

m-Steiner巡回セールスマン問題のための漸近的にタイトなオンラインアルゴリズム【JST・京大機械翻訳】

An asymptotically tight online algorithm for m-Steiner Traveling Salesman Problem

著者 (4件)： Zhang Yubai (Department of Mathematics, East China University of Science and Technology, Shanghai, 200237, People’s Republic of China) ,  Zhang Zhao (College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua, Zhejiang, 321004, People’s Republic of China) ,  Liu Zhaohui (Department of Mathematics, East China University of Science and Technology, Shanghai, 200237, People’s Republic of China) ,  Chen Qirong (College of Mathematics and Computer Science, Shangrao Normal University, Shangrao, Jiangxi, 334001, People’s Republic of China)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 174  ページ： Null  発行年： 2022年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文は,オンラインエッジ閉塞によるm-Steiner Traveling Salesman問題を研究した。短期間で回復不能な道路にいくつかの閉塞があるという仮定の下で,Min-Maxオンラインm-Steiner Salesman問題(MinMax-mSTSPonline)の目標は,mセールスの最大コストができるだけ少なくても,少なくとも1回,各顧客を訪問するm閉鎖トゥールを見つけることである。という前提の下では,最小1回,M-Maxオンラインm-Steiner Salesman問題(MinMax-mSTSPonline)の目標は,少なくとも1回,各顧客を訪問する。オンラインアルゴリズムを与え,その競合比がm≧2でk-1m+10,m=1でk+2であり,kが閉塞数であることを示した。この比は,この問題の下限[km]+1が,得られたので,漸近的に緊密である。Copyright 2021 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *巡回セールスマン問題 ,  道路
準シソーラス用語： *オンラインアルゴリズム ,  競合比 ,  Max ,  *オンライン , 【Automatic Indexing@JST】

著者キーワード (4件)： アルゴリズムの解析 ,  オンラインアルゴリズム ,  Steiner巡回セールスマン問題 ,  閉塞

分類 (4件)： ネットワーク法  (KA03040X) ,  数値計算  (JE02000J) ,  人工知能  (JE08000Z) ,  計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 巡回セールスマン問題 ,  オンラインアルゴリズム