文献

J-GLOBAL ID：202202284112738660   整理番号：22A0495863

多重被覆制約を持つ頂点被覆のための近似アルゴリズム【JST・京大機械翻訳】

Approximation Algorithm for Vertex Cover with Multiple Covering Constraints

著者 (2件)： Hung Eunpyeong (Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan) ,  Kao Mong-Jen (Department of Computer Science, National Yang-Ming Chiao-Tung University, Hsinchu, Taiwan)
資料名： Algorithmica  (Algorithmica)
巻： 84  号： 1  ページ： 1-12  発行年： 2022年 
JST資料番号： T0530A  ISSN： 0178-4617  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： ハイパーグラフにおける多重カバレッジ制約を伴う頂点カバー問題を考察した。この問題において,最大エッジサイズf,コスト関数[数式:原文を参照],およびEのエッジ部分集合[数式:原文を参照]を有する超グラフ[数式:原文を参照]を,各部分集合に対する要求[数式:原文を参照]をカバーするとともに与えた。目的は,各エッジ部分集合[数式:原文を参照]に対して,少なくとも[数式:原文を参照]エッジがSによってカバーされるようなVの最小コスト部分集合Sを見つけることである。この問題は,古典的頂点カバー問題の基本だが一般的形式であり,Beraらによって考慮されたエッジ分割頂点カバー問題であった。[数式:原文を参照]が[数式:原文を参照]調和数である,この問題に対する[数式:原文を参照]近似を生成するプライマ-二重アルゴリズムを示した。これは,[数式:原文を参照]の以前の比を超えて改善し,そこでは,cがモンテカルロランダム化アルゴリズムの低い故障確率を確保するために使用された大きな定数である。以前の結果と比較して,著者らのアルゴリズムは決定論的で純粋なコンビナトリアルであり,Ellipsoidソルバが本基本問題のために必要でないことを意味した。この結果は,LPプリマリティの言語を用いたいくつかの古典的タイト結果の新しい再解釈として見ることができる。Copyright The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： モンテカルロ法 ,  *アルゴリズム ,  言語 ,  故障率 ,  *被覆 ,  *近似法 ,  費用関数 ,  *多重化 ,  超グラフ
準シソーラス用語： *近似アルゴリズム ,  ソルバ ,  決定論 , 【Automatic Indexing@JST】

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

タイトルに関連する用語 (4件)： 多重 ,  制約 ,  頂点被覆 ,  近似アルゴリズム