|
|
Seminar of Control System Department
December 15, 2016 12:00, Ekaterinburg, ul. S Kovalevskoi, 16, room 322
|
|
|
|
|
|
State cost estimation and early stopping of DP procedure for TSPs with profits
Ya. V. Salii |
Number of views: |
This page: | 101 |
|
Abstract:
Continuing the series on DP for TSPs with profits (Orienteering
Problem of not surpassing a certain threshold on the cost defined on
the arcs of the graph while maximizing the profits defined on the
graph's nodes and Prize Collecting TSP of minimizing the costs while
surpassing a certain profit threshold), we present our results on
estimating the cost of states and terminating the algorithm early,
without having to calculate the costs for all of the states of the
corresponding TSP—all of that for the mere metricity of the cost
function.
|
|