Art

J-GLOBAL ID：201402262339806329   Reference number：14A0891232

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

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

Author (1)： UENO Kenya (Kyoto Univ.)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 114  Issue： 80(COMP2014 8-14)  Page： 61-67  Publication year： Jun. 06, 2014 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *0-1 integer programming ,  *constraint condition (restriction) ,  equivalency ,  exact solution ,  optimization problem ,  *fast algorithm ,  *feasibility ,  computational complexity ,  information retrieval ,  NP hard ,  vector (mathematics) ,  equality constraints
Semi thesaurus term： exact algorithm ,  Exhaustive Search

JST classification (2)： Mathematical programmings  (KA03030M) ,  Theory of computation  (JB02000A)

Reference (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).

Terms in the title (4)： 線形 ,  等式制約 ,  0-1整数計画法 ,  厳密アルゴリズム