文献

J-GLOBAL ID：202002215552825123   整理番号：20A1758772

最密k-部分グラフへの応用を伴うLP-ラウンドプラスGreedによるMax k-Uncutの近似【JST・京大機械翻訳】

Approximating Max k-Uncut via LP-rounding Plus Greed, with Applications to Densest k-Subgraph

著者 (2件)： Zhang Peng (School of Software, Shandong University, Jinan, Shandong, China) ,  Liu Zhendong (School of Computer Science and Technology, Shandong Jianzhu University, Jinan, Shandong, China)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12290  ページ： 161-172  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： [数式:原文を参照]問題は大規模ネットワークのホモフィリンの研究から生じる。エッジ上に定義された非負重みを持つn-頂点無向グラフ[数式:原文を参照]と,正の整数kを与えられた場合,[数式:原文を参照]問題は,カットされないエッジの全重みが最大化されるように,Vの分割[数式:原文を参照]を見つける。また,[数式:原文を参照]は,解におけるカットエッジの全重みである測度によるクラスタリング問題として見なせる。この問題は古典的[数式:原文を参照]問題の補完であり,最も密な[数式:原文を参照]問題と驚くほど豊富な接続を持つことを証明した。本論文では,LPラウンドと greedy欲戦略を組み合わせた非一様アプローチを用いて,[数式:原文を参照]に対する近似アルゴリズムを与えた。制約kの限られた違反により,[数式:原文を参照]に対する良好な期待近似比[数式:原文を参照]を示した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 測度 ,  *近似法 ,  クラスタ化 ,  無向グラフ ,  *部分グラフ
準シソーラス用語： 近似アルゴリズム ,  大規模ネットワーク , 【Automatic Indexing@JST】

著者キーワード (4件)： 最大k-uncut ,  高密度k-部分グラフ ,  近似アルゴリズム ,  組合せ最適化

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

タイトルに関連する用語 (5件)： 部分グラフ ,  応用 ,  LP ,  Max ,  近似