論理回路の最大消費電力問題の近似可能性について

• Item type: SIG Technical Reports(1)
• 公開日: 2000-03-21
• タイトル: 論理回路の最大消費電力問題の近似可能性について
• タイトル / 言語: en
• タイトル: The approximability of MAX Power Consumption Problem of Logic Circuits
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学
• 著者所属: 京都大学
• 著者所属: 京都大学／現在はアイスランド大学
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者名: 松田, 健; 岩間, 一雄; ハルダースソンマグナス
• 著者名(英): Takeshi, Matsuda; Kazuo, Iwama; MagnÚS, M.HalldÓRsson
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 論理回路の最大消費電力問題とは、与えられた論理回路に対して、その消費電力を最大化する入力値のペアを求める問題である。一般の回路の場合には、この問題に対する近似度m-<1ε>以下のアルゴリズムは存在しないことが簡単にわかる。そこで、我々の研究では対象とする回路をAND一段のみの回路に制限する。この制限のもとでの最大消費電力問題を0、1、u、dの4値を使用する式の最大充足化問題として定式化した。まず、この問題がNP困難であることを証明する。次に、近似アルゴリズムとして、変数の肯定・否定がバランスよく現れる場合には比較的よい近似度が得られることを示す。一般の場合に対する近似度1.98のアルゴリズムも与える。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: MAX Power Consumption Problem of Logic Circuits is the problem of estimating the maximum power consumption of a given logic circuit. It is easy to see that this problem for general circuits is hard to approximate within a factor of m^<1-ε>. So we consider restricted circuits that consist of only one level of AND gates. We formalize this problem as a kind of MAX SAT problem, using four values 0, 1, u and d. We first prove that this problem is NP-hard. As for approximation algorithms, we consider two cases, the case that positive and negative appearances of each variable are well balanced and the general case. We can obtain a relatively good approximation factor for the balanced case and a factor of 1.98 for the general case.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2000, 号 31(1999-AL-072), p. 9-16, 発行日 2000-03-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会