文献

J-GLOBAL ID：202002281464635719   整理番号：20A1490114

ナップサック多面体における格子点への距離【JST・京大機械翻訳】

Distances to lattice points in knapsack polyhedra

著者 (3件)： Aliev Iskander (Mathematics Institute, Cardiff University, Cardiff, UK) ,  Henk Martin (Department of Mathematics, TU Berlin, Berlin, Germany) ,  Oertel Timm (Mathematics Institute, Cardiff University, Cardiff, UK)
資料名： Mathematical Programming  (Mathematical Programming)
巻： 182  号： 1-2  ページ： 175-198  発行年： 2020年 
JST資料番号： B0847B  ISSN： 0025-5610  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： ナップサック多面体の頂点からその最近接格子点までの[数式:原文を参照]距離に対する最適上限を与えた。ランダム化設定では,上限が平均で著しく改善されることを示した。コロールとして,整数ナップサック問題の付加的積分ギャップに対する最適上限を得て,「典型的」ナップサック問題の積分ギャップが最悪ケースシナリオで生じる積分ギャップよりも劇的に小さいことを示した。また,一般的事例において,整数計画ギャップが自然な最適下限をアドミットすることを証明した。Copyright The Author(s) 2019 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 整数計画法 ,  *ナップサック問題

著者キーワード (3件)： 90C10 ,  52C07 ,  11H31

分類 (5件)： 数理計画法  (KA03030M) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  システム最適化手法  (IA02050Z) ,  計算理論  (JB02000A) ,  数値計算  (JE02000J)

物質索引 (1件)： コロール

タイトルに関連する用語 (3件)： ナップ ,  サック ,  多面体