| Comparative analysis of efficiency of different variants of the dynamic programming method for solving the problem of optimal placing of elements on the chip |
|
|
| Authors |
| | Posypkin M.A. |
| | Si Thu Thant Sin |
| Date of publication |
| | 2014 |
|
| Abstract |
| | One of the stages of the integrated circuits design is a stage of the deployment of its elements on the chip. Formally, the problem of this type can be considered as the task of discrete optimization knapsack-like problem. One of the basic methods of solution of such problems is the method of dynamic programming. The work is dedicated to the comparative study of different serial variants of the method of dynamic programming for a task knapsack. The paper gives formulation of the problem, describes the main variants of the method of dynamic programming, presents experimental comparison on the randomly generated instances. At the end the paper draw conclusions about the comparative efficiency of different variants of dynamic programming. |
| Keywords |
| | knapsack problem, dynamic programming, discrete optimization |
| Library reference |
| | Posypkin M.A., Si Thu Thant Sin Comparative analysis of efficiency of different variants of the dynamic programming method for solving the problem of optimal placing of elements on the chip // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2014. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2014. Part 2. P. 97-100. |
| URL of paper |
| | http://www.mes-conference.ru/data/year2014/pdf/D125.pdf |
