文献

J-GLOBAL ID：201902240345127272   整理番号：19A2521565

被覆型k-破れ線形プログラムのための近似アルゴリズム【JST・京大機械翻訳】

Approximation algorithms for the covering-type k-violation linear program

著者 (3件)： Takazawa Yotaro (Department of Industrial Engineering and Economics, Tokyo Institute of Technology, Tokyo, Japan) ,  Mizuno Shinji (Department of Industrial Engineering and Economics, Tokyo Institute of Technology, Tokyo, Japan) ,  Kitahara Tomonari (Department of Industrial Engineering and Economics, Tokyo Institute of Technology, Tokyo, Japan)
資料名： Optimization Letters  (Optimization Letters)
巻： 13  号： 7  ページ： 1515-1521  発行年： 2019年 
JST資料番号： W4817A  ISSN： 1862-4472  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： ここでは,制約の大部分が破れることができるカバー型k-違反線形プログラムを研究した。この問題は混合整数計画として定式化され,NP困難であることが知られている。本論文では,自然LP緩和を用いた簡単な[数式:原文を参照]近似アルゴリズムを提案した。LP緩和の積分ギャップは[数式:原文を参照]であることも示した。このことは,最適値の下限としてLP緩和を用いるとき,より良い近似アルゴリズムを得ることができないことを意味する。Copyright 2019 Springer-Verlag GmbH Germany, part of Springer Nature Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *線形性 ,  緩和現象 ,  積分 ,  *被覆 ,  整数計画法 ,  定式化 ,  *アルゴリズム ,  NP困難 ,  最適値 ,  *近似アルゴリズム

著者キーワード (5件)： 近似アルゴリズム ,  混合整数プログラム ,  k-破れ線形プログラム ,  線形緩和 ,  丸めアルゴリズム

分類 (1件)： 数理計画法  (KA03030M)

タイトルに関連する用語 (2件)： 線形 ,  近似アルゴリズム