|
|
Seminar of Control System Department
April 23, 2015 12:00–14:00, Ekaterinburg, ul. S Kovalevskoi, 16, room 322
|
|
|
|
|
|
On a "double-edged" parallel implementation of a sort of dynamic programming for precedence constrained routing problems
Ya. V. Salii |
Number of views: |
This page: | 102 |
|
Abstract:
We are going to present a yet another way of conducting dynamic programming for precedence constrained routing problems in parallel. The method is based on the "divide and conquer" strategy proposed in (Lawler, 1979) without proof of its validity. The idea of the method is to run both forward and backwards DP for the problem in parallel until the "middle" of the problem and then to "join" the obtained solutions. A proof of validity for the method will be presented.
|
|