PIPELINE ARCHITECTURES FOR DYNAMIC-PROGRAMMING ALGORITHMS

被引：15
作者：
CHEN, GH [1 ]
CHERN, MS [1 ]
JANG, JH [1 ]
机构：
[1] NATL TSING HUA UNIV,DEPT IND ENGN,HSINCHU 300,TAIWAN
来源：
PARALLEL COMPUTING | 1990年 / 13卷 / 01期
关键词：
knapsack problems; dynamic programming; Pipelined computation;
D O I：
10.1016/0167-8191(90)90124-R
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Dynamic programming is one of the most powerful approaches to many combinatorial optimization problems. In this paper, we present pipeline architectures for the dynamic programming algorithms for the knapsack problems. They enable us to achieve an optimal speedup using processor arrays, queues, and memory modules. The processor arrays can be regarded as pipelines where the dynamic programming algorithms are implemented through pipelining. © 1990.
引用
收藏
页码：111 / 117
页数：7
相关论文
共 50 条
[31]   FUZZY DYNAMIC-PROGRAMMING - AN APPLICATION TO UNIT COMMITMENT [J].
SU, CC ;
HSU, YY .
IEEE TRANSACTIONS ON POWER SYSTEMS, 1991, 6 (03) :1231-1237
[32]   USING GEOMETRIC TECHNIQUES TO IMPROVE DYNAMIC-PROGRAMMING ALGORITHMS FOR THE ECONOMIC LOT-SIZING PROBLEM AND EXTENSIONS [J].
VANHOESEL, S ;
WAGELMANS, A ;
MOERMAN, B .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 75 (02) :312-331
[33]   DYNAMIC-PROGRAMMING FOR DETECTING, TRACKING, AND MATCHING DEFORMABLE CONTOURS [J].
GEIGER, D ;
GUPTA, A ;
COSTA, LA ;
VLONTZOS, J .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1995, 17 (03) :294-302
[34]   STOCHASTIC DYNAMIC-PROGRAMMING TO SUPPORT SOW REPLACEMENT DECISIONS [J].
HUIRNE, RBM ;
DIJKHUIZEN, AA ;
VANBEEK, P ;
HENDRIKS, THB .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 67 (02) :161-171
[35]   GENERATION OF TEMPORAL SEQUENCES USING LOCAL DYNAMIC-PROGRAMMING [J].
BORGHESE, NA ;
ARBIB, MA .
NEURAL NETWORKS, 1995, 8 (01) :39-54
[36]   A dynamic-programming algorithm for hierarchical discretization of continuous attributes [J].
Shen, Ching-Cheng ;
Chen, Yen-Liang .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 184 (02) :636-651
[37]   An Approximate Dynamic-Programming Approach to the Joint Replenishment Problem [J].
Segev, Danny .
MATHEMATICS OF OPERATIONS RESEARCH, 2014, 39 (02) :432-444
[38]   INCORPORATING RISK-AVERSION INTO DYNAMIC-PROGRAMMING MODELS [J].
KRAUTKRAEMER, JA ;
VANKOOTEN, GC ;
YOUNG, DL .
AMERICAN JOURNAL OF AGRICULTURAL ECONOMICS, 1992, 74 (04) :870-878
[39]   EXISTENCE WITHOUT EXPLICIT COMPACTNESS IN STOCHASTIC DYNAMIC-PROGRAMMING [J].
BALDER, EJ .
MATHEMATICS OF OPERATIONS RESEARCH, 1992, 17 (03) :572-580
[40]   A DYNAMIC-PROGRAMMING METHOD FOR SINGLE-MACHINE SCHEDULING [J].
IBARAKI, T ;
NAKAMURA, Y .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 76 (01) :72-82
12345