Presentation | 2015-07-17 [Invited Talk] Exploiting ZDDs on Constrained Dynamic Programming Problems Norihito Yasuda, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Dynamic Programming is a fundamental tool for many optimization problems. However, in practical situations, in addition to textbook style settings, problems contain their own specific constraints. In most of such cases, unfortunately we cannot apply conventional dynamic programming-based techniques due to the additional constraint. In this talk, I briefly introduce our recent studies on combinatorial optimizations by giving an example of 0-1 Knapsack Problem. The basic idea of our approach is that we represent constraints by Zero-suppressed Binary Decision Diagram (ZDD) and use it as a `guide’ of the dynamic programming paths. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Dynamic Programming / Zero-Suppressed Binary Decision Diagram / ZDD / Knapsack Problem |
Paper # | IN2015-34 |
Date of Issue | 2015-07-09 (IN) |
Conference Information | |
Committee | IN |
---|---|
Conference Date | 2015/7/16(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Hokkaido University |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | Cloud Networking, SDN, OpenFlow, Virtual Private Network (VPN), Overlay Network/P2P, Network configuration, etc. |
Chair | Hidetsugu Kobayashi(NTT) |
Vice Chair | Katsunori Yamaoka(Tokyo Inst. of Tech.) |
Secretary | Katsunori Yamaoka(NTT) |
Assistant | Yuichi Sudo(NTT) / Kunitake Kaneko(Keio Univ.) |
Paper Information | |
Registration To | Technical Committee on Information Networks |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | [Invited Talk] Exploiting ZDDs on Constrained Dynamic Programming Problems |
Sub Title (in English) | |
Keyword(1) | Dynamic Programming |
Keyword(2) | Zero-Suppressed Binary Decision Diagram |
Keyword(3) | ZDD |
Keyword(4) | Knapsack Problem |
1st Author's Name | Norihito Yasuda |
1st Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
Date | 2015-07-17 |
Paper # | IN2015-34 |
Volume (vol) | vol.115 |
Number (no) | IN-140 |
Page | pp.pp.67-72(IN), |
#Pages | 6 |
Date of Issue | 2015-07-09 (IN) |