文献

J-GLOBAL ID：202202278430762717   整理番号：22A1115468

方向付けとk-TSPのための高速アルゴリズム【JST・京大機械翻訳】

Faster algorithms for orienteering and k-TSP

著者 (3件)： Gottlieb Lee-Ad (Ariel University, Israel) ,  Krauthgamer Robert (Weizmann Institute of Science, Israel) ,  Rika Havana (Weizmann Institute of Science, Israel)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 914  ページ： 73-83  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ユークリッド空間における根付き方向付け問題を考察した:Rdにおけるn点P,根点s∈Pおよび予算B>0は,sから始まる経路を発見し,ほとんどのBで全長さを持ち,できるだけ多くのP点として訪問する。この問題はNP困難であり,従って,(1-δ)近似アルゴリズムを研究した。この問題に対する以前の多項式時間近似スキーム(PTAS)は,ChenとHar-Peled(2008),時間nO(dd/δ)_2(d/δ)O(d)で実行され,この時間境界の改善が開放問題として残された。著者らの主な寄与は,nO(1/δ)_2(d/δ)O(d)の時間複雑性が有意に改善したPTASである。配向問題を近似する既知の技法は,根付きk-TSPの1/δ相関インスタンス(k-TSPトーラスは少なくともkポイントで訪問するもの)を解くためにそれを低減することである。しかし,この低減におけるk-TSPトーラスは,ある過剰な保証(すなわち,それらの長さは,通常(1+δ)近似より強力である)のパラメータに比例して最適長さを超過する。著者らの主な技術的寄与は,特に次元dへの依存性において,これらのk-TSP変異体の実行時間を改善することである。実際,著者らの実行時間は,d=O(1)の代わりにd=O(loglogn)まで,適度に大きい次元に対してさえも多項式である。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  時間 ,  多項式 ,  近似法 ,  計算理論 ,  *高速アルゴリズム ,  Euclid空間 ,  δ相 ,  NP困難
準シソーラス用語： 近似アルゴリズム ,  実行時間 ,  複雑性 ,  多項式時間 ,  トーラス , 【Automatic Indexing@JST】

著者キーワード (3件)： オリエンテーリング ,  k-TSP ,  平面掃引アルゴリズム

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (1件)： 高速アルゴリズム