WEKO3
アイテム
A Recursive Framework for Evaluating Moments Using Zero-Suppressed Binary Decision Diagrams
http://hdl.handle.net/10061/0002000778
http://hdl.handle.net/10061/000200077868a7e15f-1496-48e3-9831-12cebc871b3f
| アイテムタイプ | 学術雑誌論文 / Journal Article(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2025-02-17 | |||||||||||
| タイトル | ||||||||||||
| タイトル | A Recursive Framework for Evaluating Moments Using Zero-Suppressed Binary Decision Diagrams | |||||||||||
| 言語 | ||||||||||||
| 言語 | eng | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | Discrete optimization | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | family operation | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | method of moments | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | zero-suppressed binary decision diagram | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ | journal article | |||||||||||
| アクセス権 | ||||||||||||
| アクセス権 | open access | |||||||||||
| 著者 |
Lim, Brian Godwin
× Lim, Brian Godwin
× Tan, Renzo Roel× Kawahara, Jun
× Minato, Shin-Ichi
× 池田, 和司 |
|||||||||||
| 抄録 | ||||||||||||
| 内容記述タイプ | Abstract | |||||||||||
| 内容記述 | The zero-suppressed binary decision diagram (ZDD) is a compact data structure widely used for the efficient representation of families of sparse subsets. Its inherent recursive structure also facilitates easy diagram manipulation and family operations. Practical applications generally fall under discrete optimization, such as combinatorial problems and graph theory. Given its utility, summarizing the subsets represented in the diagram using key metrics is of great value as this provides valuable insights into the characteristics of the family. The paper proposes a recursive algorithm to extract information on moments from families represented as a ZDD. Given a value for every element in the universe, the value of a subset is first formulated as the sum of the values of its elements. The moments of a family are then calculated as the mean of the exponentiated subset values, akin to the method of moments. Leveraging the structure of the ZDD, the proposed algorithm recursively traverses a given diagram for efficient moments evaluation via multinomial expansion. Its utility is then demonstrated with three classical problems$2014power sets, the knapsack problem, and paths in graphs$2014offering orders of magnitude increase in computational efficiency relative to conventional method. Overall, the proposed algorithm enhances the functionality of the ZDD by introducing an efficient family operation to uncover the distribution of subset values in a represented family. | |||||||||||
| 書誌情報 |
en : IEEE Access 巻 12, p. 91886-91895, 発行日 2024-07-01 |
|||||||||||
| 出版者 | ||||||||||||
| 出版者 | IEEE | |||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||
| 収録物識別子 | 2169-3536 | |||||||||||
| 出版者版DOI | ||||||||||||
| 関連タイプ | isReplacedBy | |||||||||||
| 識別子タイプ | DOI | |||||||||||
| 関連識別子 | https://doi.org/10.1109/ACCESS.2024.3421676 | |||||||||||
| 出版者版URI | ||||||||||||
| 関連タイプ | isReplacedBy | |||||||||||
| 識別子タイプ | URI | |||||||||||
| 関連識別子 | https://ieeexplore.ieee.org/document/10579738 | |||||||||||
| 権利 | ||||||||||||
| 権利情報Resource | https://creativecommons.org/licenses/by-nc-nd/4.0/ | |||||||||||
| 権利情報 | c 2024 The Authors. This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License. For more information, see https://creativecommons.org/licenses/by-nc-nd/4.0/ | |||||||||||
| 著者版フラグ | ||||||||||||
| 出版タイプ | NA | |||||||||||
