Oleg Burdakov

Abstract.    We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard. Only heuristics can be applied in the case of its instances whose size is beyond the capacity of the existing exact algorithms. The hop-constrained DSTP is viewed as a bi-criteria problem in which the tree cost and the number of hops are minimized. We derive optimality conditions and use them for developing an approach aimed at approximately solving hop-constrained DSTP. The approach can also be used for improving approximate solutions produced by other heuristic algorithms or as a part of exact algorithms. Specific label-correcting-type algorithms based on this approach will be presented, and preliminary results of their performance on a set of test problems will be reported. The test instances originate from 3D placement of unmanned aerial vehicles used for multi-target surveillance. They are characterized by a relatively small number of terminal nodes and a very large number of nodes and a huge number of arcs (above 10^8).