• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Oleg Burdakov


Linkoping University, Sweden
 

A bi-criteria approach to solving huge hop-constrained Steiner tree problems

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).

 





 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!
To be used only for spelling or punctuation mistakes.