文献

J-GLOBAL ID：201902213806407849   整理番号：19A0875409

線形計画問題のための単純射影アルゴリズム【JST・京大機械翻訳】

A Simple Projection Algorithm for Linear Programming Problems

著者 (2件)： Kitahara Tomonari (Department of Economic Engineering, Faculty of Economics, Kyushu University, Fukuoka-shi, Fukuoka, Japan) ,  Sukegawa Noriyoshi (Department of Information and System Engineering, Faculty of Science and Engineering, Chuo University, Bunkyo-ku, Tokyo, Japan)
資料名： Algorithmica  (Algorithmica)
巻： 81  号： 1  ページ： 167-178  発行年： 2019年 
JST資料番号： T0530A  ISSN： 0178-4617  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 藤ishiらは線形計画問題(LP)のための新しいアルゴリズムであるLP-Newton法を提案した。それらは,各変数に対してより低い上限を持ち,関連するzonotopeを導入することにより問題を再定式化する。LP-Newton法はWolfeのアルゴリズムによりzonotope上への射影を繰り返す。LP-Newton法に対しては,藤ishiらは,アルゴリズムが有限数の反復で終了することを示した。さらに,すべての入力が有理数であるならば,Lが問題の入力長であるLにおいて,射影の数が多項式によって制限されることを示した。本論文では,二値探索を用いたアルゴリズムへの修正を提案した。その有限性に加えて,すべての入力が有理数であり,最適値が整数であるならば,射影の数は[数式:原文を参照]によって制限される。すなわち,線形結合である。Copyright 2018 Springer Science+Business Media, LLC, part of Springer Nature Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  有理数 ,  多項式 ,  定式化 ,  有限性 ,  *線形計画法 ,  *射影 ,  線形結合 ,  最適値

著者キーワード (4件)： 線形計画法 ,  ゾノトープ ,  投影 ,  二値探索

分類 (2件)： 分子・遺伝情報処理  (JE15040B) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (4件)： 線形計画 ,  問題 ,  射影 ,  アルゴリズム