文献

J-GLOBAL ID：202002248652205828   整理番号：20A0769531

確率点に対する最も有望なスカイライン問題【JST・京大機械翻訳】

The most-likely skyline problem for stochastic points

著者 (4件)： Agrawal Akash (Dept. of Computer Science&Engineering, University of Minnesota-Twin Cities, Minneapolis, MN, 55455, USA) ,  Li Yuan (Dept. of Computer Science&Engineering, University of Minnesota-Twin Cities, Minneapolis, MN, 55455, USA) ,  Xue Jie (Dept. of Computer Science&Engineering, University of Minnesota-Twin Cities, Minneapolis, MN, 55455, USA) ,  Janardan Ravi (Dept. of Computer Science&Engineering, University of Minnesota-Twin Cities, Minneapolis, MN, 55455, USA)
資料名： Computational Geometry: Theory and Applications  (Computational Geometry: Theory and Applications)
巻： 88  ページ： Null  発行年： 2020年 
JST資料番号： W0536A  ISSN： 0925-7721  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Rdにおけるn点の集合Oに対して,スカイラインはOのすべての点の部分集合から成り,そこではいかなる点もOの他の点によって支配されない。それぞれの点が存在するπ∈(0,1)の関連確率を有すると仮定した。発生の最大確率を有するスカイラインを計算する問題を考察した。Rd,d≧3において,問題はNP困難であり,望ましいスカイラインは,P=NPがなければ多項式時間でよく近似できないことを示した。R2において,最適O(nlog n)-時間とO(n)-空間アルゴリズムを与えた。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *近似法 ,  NP困難
準シソーラス用語： 多項式時間 , 【Automatic Indexing@JST】

著者キーワード (5件)： スカイライン ,  確率点 ,  NP困難性 ,  近似不能性 ,  最適アルゴリズム

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： 確率 ,  スカイライン