文献

J-GLOBAL ID：201402262339806329   整理番号：14A0891232

線形等式制約付き0-1整数計画法の厳密アルゴリズム

Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints

著者 (1件)： UENO Kenya (Kyoto Univ.)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 80(COMP2014 8-14)  ページ： 61-67  発行年： 2014年06月06日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,制約が線形等式のみである0-1整数計画法の実現可能性問題に関する,O(1.415ⁿ)時間厳密アルゴリズムを示した。アルゴリズムは全数検索よりも二次的に高速で,また,筆者らの研究を動機づけた,Impagliazzo/Lovett/Paturi/Schneider(arXiv:1401.5512)による実現可能性問題の不等式バージョンアルゴリズムよりも殆ど二次的に高速である。時間複雑性の改良よりもむしろ,厳密指数アルゴリズムに関する多くのNP困難問題を包含するという,単純な方向へと進んだ。同様に,アルゴリズムを線形等式制約付き0-1整数計画法の最適化問題へと拡張した。(翻訳著者抄録)

シソーラス用語： *0-1整数計画法 ,  *制約条件 ,  等価性 ,  厳密解 ,  最適化問題 ,  *高速アルゴリズム ,  *実現可能性 ,  計算量 ,  情報検索 ,  NP困難 ,  ベクトル
準シソーラス用語： 厳密アルゴリズム ,  全数検索 ,  等式制約

分類 (2件)： 数理計画法  (KA03030M) ,  計算理論  (JB02000A)

引用文献 (19件)：

• Bleich, C. and Overton, M.: A linear-time algorithm for the weighted median problem, Technical Report 75, Computer Science Department, Courant Institute of Mathematical Sciences, New York University (1983).
• Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L. and Tarjan, R. E.: Linear time bounds for median computations, Proceedings of the 40th annual ACM symposium on Theory of computing (STOC 1972), ACM, pp. 119-124 (1972).
• Byskov, J. M., Madsen, B. A. and Skjernaa, B.: New algorithms for exact satisfiability, Theoretical Computer Science, Vol. 332, No. 1, pp. 515-541 (2005).
• Drori, L. and Peleg, D.: Faster exact solutions for some NP-hard problems, Theoretical Computer Science, Vol. 287, No. 2, pp. 473-499 (2002).
• Fliege, J.: A randomized parallel algorithm with run time O(n²) for solving an n × n system of linear equations, arXiv preprin arXiv: 1209.3995 (2012).

タイトルに関連する用語 (4件)： 線形 ,  等式制約 ,  0-1整数計画法 ,  厳密アルゴリズム