文献

J-GLOBAL ID：202202222275291277   整理番号：22A0904196

最大曝露問題【JST・京大機械翻訳】

The maximum exposure problem

著者 (3件)： Kumar Neeraj (Department of Computer Science, University of California, Santa Barbara, USA) ,  Sintos Stavros (Duke University, Durham, NC, USA) ,  Suri Subhash (Department of Computer Science, University of California, Santa Barbara, USA)
資料名： Computational Geometry: Theory and Applications  (Computational Geometry: Theory and Applications)
巻： 104  ページ： Null  発行年： 2022年 
JST資料番号： W0536A  ISSN： 0925-7721  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 平面における一組の点Pと軸整列長方形Rを与えられた場合,点p→πPは,それがRにおいてすべての長方形の外側にあるならば,露出と呼ばれる。最大曝露問題において,整数パラメータkを与えて,著者らは,曝露点の数を最大化するために,Rからk長方形を削除することを試みた。問題はNP困難であり,Rの長方形が2つの固定長方形の翻訳である場合でも,妥当な計算量推定が近似するのが難しいことを示した。しかしながら,Rが単一長方形の翻訳だけから成るならば,多項式時間近似方式を提示する。一般的長方形によって定義された範囲空間のために,著者らは単純なO(k)二基準近似アルゴリズムを提示した。O(k2)長方形を削除することによって,著者らは,点の最適数の少なくともΩ(1/k)を露出することができた。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アラインメント ,  *近似法 ,  計算量 ,  パラメータ ,  NP困難
準シソーラス用語： 近似アルゴリズム ,  多項式時間 , 【Automatic Indexing@JST】

著者キーワード (5件)： 最大曝露 ,  PTAS ,  高密度k部分グラフ ,  幾何学的拘束除去 ,  ネットワーク回復力

分類 (2件)： 計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (1件)： 曝露