Greedy algorithms for the on-line steiner tree and generalized steiner problems

We study the on-line Steiner tree problem on a general metric space

Jeffery Westbrook

2012

Scholarcy highlights

  • We consider the on-line generalized Steiner problem on a general metric space
  • We study the on-line Steiner tree problem on a general metric space
  • We show that a class of greedy on-line algorithms are O(log(d/zs))-competitive and no deterministic algorithm is better than Ω(log(d/zs))-competitive, where s is the number of regular nodes, d the maximum metric distance between any two revealed nodes and z the optimal off-line cost
  • We show that a class of lazy and greedy on-line algorithms are O(√k · log k)-competitive and no on-line algorithms is better than Ω(log k)-competitive, where k is the number of distinct nodes that appear in the request sequence
  • These are the first algorithms for this problem

Need more features? Save interactive summary cards to your Scholarcy Library.