文献

J-GLOBAL ID：202102289110912178   整理番号：21A0353112

メトリック三角形パッキングのためのランダム化近似アルゴリズム【JST・京大機械翻訳】

A randomized approximation algorithm for metric triangle packing

著者 (5件)： Chen Yong (Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China) ,  Chen Zhi-Zhong (Division of Information System Design, Tokyo Denki University, Saitama, Japan) ,  Lin Guohui (Department of Computing Science, University of Alberta, Edmonton, AB, Canada) ,  Wang Lusheng (Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China) ,  Zhang An (Department of Mathematics, Hangzhou Dianzi University, Hangzhou, China)
資料名： Journal of Combinatorial Optimization  (Journal of Combinatorial Optimization)
巻： 41  号： 1  ページ： 12-27  発行年： 2021年 
JST資料番号： W1143A  ISSN： 1382-6905  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 3n頂点上のエッジ加重完全グラフGを与えられた場合,これらのn三角形におけるエッジの全重みが最大になるような,Gにおけるn頂点-離散三角形の収集のための最大重み三角形パッキング問題は,最大である。問題は文献において広く研究されているが,この研究の前に,入力グラフのエッジ重みが三角形不等式を満たす,そのメトリックケースに対して,非自明な近似アルゴリズムが設計され,解析されていないことは驚くべきことである。本論文では,最大重みメトリック三角形パッキング問題に対する最初の非自明多項式時間近似アルゴリズムを設計した。提案アルゴリズムをランダム化し,任意の一定[数式:原文を参照]に対する[数式:原文を参照]の予想近似比を達成した。Copyright Springer Science+Business Media, LLC, part of Springer Nature 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  不等式 ,  *近似法 ,  完全グラフ ,  パッキング問題
準シソーラス用語： *近似アルゴリズム ,  多項式時間 ,  *ホップ数 ,  ランダム化 , 【Automatic Indexing@JST】

著者キーワード (5件)： 三角形パッキング ,  計量 ,  近似アルゴリズム ,  ランダムアルゴリズム ,  最大サイクルカバー

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

タイトルに関連する用語 (4件)： メトリック ,  三角形 ,  ランダム化 ,  近似アルゴリズム