文献

J-GLOBAL ID：202202287438764530   整理番号：22A0310879

増分ナップザック制約の下での分数部分加法的最大化【JST・京大機械翻訳】

Fractionally Subadditive Maximization Under an Incremental Knapsack Constraint

著者 (3件)： Disser Yann (TU Darmstadt, Darmstadt, Germany) ,  Klimm Max (TU Berlin, Berlin, Germany) ,  Weckbecker David (TU Darmstadt, Darmstadt, Germany)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12982  ページ： 206-223  発行年： 2022年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 時間的に成長するナップサック制約の下で,分数サブ加算関数を最大化する問題を考察した。この問題に対する増分解を,地盤集合の要素を含む順序によって与え,増分解の競合比を,対応する容量の最適解と比較して,すべての容量に対する最悪比によって定義した。単一トン集合の値が[1,M]の範囲にあるという仮定の下で,ほとんどの[数式:原文を参照]で競合比の増分解を見つけるアルゴリズムを提示し,達成可能な競合比に関して[数式:原文を参照]の下限を与えた。さらに,このフレームワークは2つの頂点間のポテンシャルベースフローを捕捉し,単位容量を持つ古典的フローの増分最大化のために2の厳密な境界を与える。Copyright Springer Nature Switzerland AG 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  時間 ,  容量 ,  問題 ,  下限 ,  *加算 ,  *制約条件
準シソーラス用語： 最適解 ,  競合比 ,  バックパック , 【Automatic Indexing@JST】

著者キーワード (5件)： 増分最大化 ,  ナップザック制約 ,  分数部分加算 ,  競争比 ,  ポテンシャルベースの流れ

分類 (2件)： 符号理論  (ND02030R) ,  数値計算  (JE02000J)

タイトルに関連する用語 (6件)： 増分 ,  ナップザック ,  制約 ,  分数 ,  加法 ,  最大化