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

• Item type: SIG Technical Reports(1)
• 公開日: 2014-06-06
• タイトル: Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
• タイトル / 言語: en
• タイトル: Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: The Hakubi Center for Advanced Research, Kyoto University
• 著者所属(英): en
• 著者所属(英): The Hakubi Center for Advanced Research, Kyoto University
• 著者名: Kenya, Ueno
• 著者名(英): Kenya, Ueno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In this paper, we show an O(1.415n)-time exact algorithm for the feasibility problem of 0-1 integer programs whose constraints are only linear equalities. The algorithm is quadratically faster than exhaustive search and also almost quadratically faster than the algorithm for an inequality version of the feasibility problem by Impagliazzo, Lovett, Paturi and Schneider (arXiv:1401.5512), which motivated our work. Rather than improving the time complexity, we advance to a simple direction as inclusion of many NP-hard problems in terms of exact exponential algorithms. We also extend our algorithm to the optimization problem of 0-1 integer programs with linear equality constraints.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we show an O(1.415n)-time exact algorithm for the feasibility problem of 0-1 integer programs whose constraints are only linear equalities. The algorithm is quadratically faster than exhaustive search and also almost quadratically faster than the algorithm for an inequality version of the feasibility problem by Impagliazzo, Lovett, Paturi and Schneider (arXiv:1401.5512), which motivated our work. Rather than improving the time complexity, we advance to a simple direction as inclusion of many NP-hard problems in terms of exact exponential algorithms. We also extend our algorithm to the optimization problem of 0-1 integer programs with linear equality constraints.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2014-AL-148, 号 10, p. 1-7, 発行日 2014-06-06
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会