文献

J-GLOBAL ID：202202216284919491   整理番号：22A0623633

線形制約を満たす重みを持ついくつかのグラフ最適化問題【JST・京大機械翻訳】

Some graph optimization problems with weights satisfying linear constraints

著者 (3件)： Nip Kameng (School of Mathematical Sciences, Xiamen University, Xiamen, China) ,  Shi Tianning (Department of Mathematical Sciences, Tsinghua University, Beijing, China) ,  Wang Zhenbo (Department of Mathematical Sciences, Tsinghua University, Beijing, China)
資料名： Journal of Combinatorial Optimization  (Journal of Combinatorial Optimization)
巻： 43  号： 1  ページ： 200-225  発行年： 2022年 
JST資料番号： W1143A  ISSN： 1382-6905  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 本論文では,頂点またはエッジの重みが線形制約(max-MLC)の下で最大マッチング問題,線形制約(min-PMLC)の下で最小完全マッチング問題,線形制約(SPLC)の下で最短経路問題,および線形制約(VCLC)の下で頂点カバー問題を含むいくつかの線形制約によって決定される変数であるいくつかのグラフ最適化問題を研究した。これらの問題の目的は,線形制約に対して実行可能であり,重みのすべての実行可能な選択の中で,対応するグラフ最適化問題の最適解を見つけることである。これらの問題はNP困難であり,一般に近似するのが難しいことを見出した。これらの知見から,それらの種々の特殊症例を探索することを提示した。特に,制約の数が固定定数であるとき,これらのすべての問題は多項式的に解けることを示した。さらに,異なる重みの総数が固定定数であるならば,最大MLC,min-PMLC,およびSPLCは多項式可解であり,VCLCは2近似アルゴリズムを持っている。さらに,最大MLCの様々なケースに対する近似アルゴリズムを提案した。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・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *最適化 ,  線形計画法 ,  多項式 ,  最短路問題 ,  *最適化問題 ,  線形性 ,  問題 ,  マッチング ,  NP困難 ,  *制約条件
準シソーラス用語： 最適解 ,  近似アルゴリズム ,  多項式時間アルゴリズム ,  最大マッチング , 【Automatic Indexing@JST】

著者キーワード (5件)： グラフ最適化 ,  線形計画法 ,  多項式時間アルゴリズム ,  近似アルゴリズム ,  計算の複雑さ

分類 (3件)： グラフ理論基礎  (IA02020S) ,  数理計画法  (KA03030M) ,  システム設計・解析  (IA02030D)

タイトルに関連する用語 (4件)： 線形 ,  制約 ,  グラフ ,  最適化問題