文献

J-GLOBAL ID：202202253796554063   整理番号：22A0806708

幾何学的環境における最小部分マルチカバーのための近似アルゴリズム【JST・京大機械翻訳】

Approximation algorithm for minimum partial multi-cover under a geometric setting

著者 (4件)： Ran Yingli (College of Mathematics and Computer Sciences, Zhejiang Normal University, Jinhua, Zhejiang, China) ,  Huang Xiaohui (Library and Information Center, Zhejiang Normal University, Jinhua, Zhejiang, China) ,  Zhang Zhao (College of Mathematics and Computer Sciences, Zhejiang Normal University, Jinhua, Zhejiang, China) ,  Du Ding-Zhu (Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA)
資料名： Optimization Letters  (Optimization Letters)
巻： 16  号： 2  ページ： 667-680  発行年： 2022年 
JST資料番号： W4817A  ISSN： 1862-4472  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 最小部分集合マルチカバー問題(MinPSMC)では,要素セットX,各要素[数式:原文を参照]に対するコスト[数式:原文を参照],各要素[数式:原文を参照]に対するカバー要求[数式:原文を参照],および整数kの収集により,[数式:原文を参照]のコストが少なくとも[数式:原文を参照]の少なくとも[数式:原文を参照]セットに属するならば,[数式:原文を参照]のコストが[数式:原文を参照]によって完全にカバーされるような少なくともk要素を完全にカバーするためのサブ収集[数式:原文を参照]を見つけることである。最近,MinPSMCが最密k-部分グラフ問題と少なくともハードであることが証明された。質問は,いくつかの幾何学的設定における問題に関するものである。本論文では,Xが平面上の点の集合であり,[数式:原文を参照]が一組の単位正方形(MinPSMC-US)であるMinPSMC問題を考察した。[数式:原文を参照]が要素xを含む集合の数であるすべての[数式:原文を参照]に対する[数式:原文を参照]が,MinPSMC-USに対する近似比[数式:原文を参照]を達成する近似アルゴリズムを設計した。Copyright The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *近似法 ,  部分グラフ ,  部分 ,  問題 ,  部分集合
準シソーラス用語： *近似アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (3件)： 部分集合マルチカバー ,  ユニット正方形 ,  近似アルゴリズム

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

タイトルに関連する用語 (4件)： 幾何学 ,  環境 ,  マルチ ,  近似アルゴリズム