Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10347623 | Computers & Operations Research | 2012 | 7 Pages |
Abstract
⺠We extend the 2-D knapsack problem to a problem on a directed acyclic graph. ⺠Objective value is a `terrace' function characterized by a set of corner points. ⺠We introduce a `scanning-wall' method to update the set of corner points efficiently. ⺠Shiftâandâmerge dynamic programming algorithm is extended to the 2-D case.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Byungjun You, Takeo Yamada,