文献

J-GLOBAL ID：202002219052446833   整理番号：20A0425852

最小充足可能性問題について【JST・京大機械翻訳】

On the Minimum Satisfiability Problem

著者 (4件)： Arif Umair (Department of Math and Computer Science, University of Lethbridge, Lethbridge, AB, Canada) ,  Benkoczi Robert (Department of Math and Computer Science, University of Lethbridge, Lethbridge, AB, Canada) ,  Gaur Daya Ram (Department of Math and Computer Science, University of Lethbridge, Lethbridge, AB, Canada) ,  Krishnamurti Ramesh (School of Computing Science, Simon Fraser University, Burnaby, BC, Canada)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12016  ページ： 269-281  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 最小充足可能性問題に対する標準定式化のLP緩和に対する最適解を特性化した。特性化に基づいて,n(m)が変数(節)の数である最適充足可能性問題の分数バージョンを解くために,[数式:原文を参照]組合せアルゴリズムを与えた。副産物として,著者らは,kが任意の節における最大数の文献である最小充足可能性問題のための[数式:原文を参照]近似アルゴリズムを得た。また,簡単な線形時間2近似アルゴリズムを与えた。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： キャラクタリゼーション ,  *充足可能性問題 ,  線形性 ,  アルゴリズム ,  定式化 ,  緩和現象
準シソーラス用語： 近似アルゴリズム ,  最適解 , 【Automatic Indexing@JST】

著者キーワード (3件)： 二重アルゴリズム ,  最小充足可能性 ,  近似アルゴリズム

分類 (3件)： 分子・遺伝情報処理  (JE15040B) ,  計算理論  (JB02000A) ,  進化論一般  (EC03010Q)

タイトルに関連する用語 (1件)： 充足可能性問題