文献

J-GLOBAL ID：202202217170786027   整理番号：22A0494593

部分集合和の変種のための代数アルゴリズム【JST・京大機械翻訳】

Algebraic Algorithms for Variants of Subset Sum

著者 (2件)： Dutta Pranjal (Chennai Mathematical Institute, Chennai, India) ,  Rajasree Mahesh Sreekumar (Indian Institute of Technology, Kanpur, India)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 13179  ページ： 237-251  発行年： 2022年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： [数式:原文を参照]を与えられた場合,Subset Sum問題([数式:原文を参照])は,[数式:原文を参照]が存在するかどうかを決定することである。Bellman(1957)は,O(nt)時間とO(t)空間でSubset Sumを解決する擬似多項式時間動的計画アルゴリズムを与えた。本研究では,サブセットSum問題のバリアントに対する探索アルゴリズムを提案した。提案アルゴリズムはkによってパラメータ化され,それは実現可能な集合の数(即ち,解の数,合計t)に与えられた上限である。ユニークな溶液を有する[数式:原文を参照]は,ランダム化還元下で既に[数式:原文を参照]困難であることを示した。これは,k,非常に興味深い,パラメータ化アルゴリズムの領域を作る。次に,著者らは,部分集合合計インスタンスのためにすべての実現可能な集合のハミング重みを見つける[数式:原文を参照]時間決定論的アルゴリズムを提示する。また,部分集合和インスタンスに対してすべての実現可能な集合を見つける[数式:原文を参照]時間と[数式:原文を参照]空間決定論的アルゴリズムを与えた。著者らのアルゴリズムは,解析的および数理論的技法を使用する。Copyright Springer Nature Switzerland AG 2022 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  内挿法 ,  パラメタリゼーション
準シソーラス用語： 探索アルゴリズム ,  多項式時間 ,  決定論 ,  パラメータ化アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (7件)： 部分集合和 ,  べき級数 ,  絶縁膜 ,  Hamming重量 ,  内挿 ,  対数空間 ,  Newton恒等式

分類 (3件)： グラフ理論基礎  (IA02020S) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 部分集合 ,  変種 ,  代数 ,  アルゴリズム