Grade of service Steiner minimum trees in the Euclidean plane (Q5953596)

Given a set \(P\) of \(n\) points in the Euclidean plane, service requests of grade \(g(p_i)\) for each \(p_i\) of \(P\) and unit costs \(c(g)\) for each grade of service \(g\), the Grade of Service Steiner Minimum Tree (GOSST) -- problem asks for a minimum cost network, interconnecting \(P\) and some Steiner points in the plane (with service request of grade 0), such that (1) Between each pair of points \(p_i\) and \(p_j\) of \(P\) there is a path. (2) Each edge \(e=(p_i,p_j\) of the connecting network is assigned a service grade \(g(e)\), which is no smaller than \(\min(g (p_i)\), \(g(p_j))\). (3) The cost of the network is minimal among all networks satisfying (1) and (2); the cost is the sum of all edge costs, where an edge \(e\) with service grade \(g(e)\) induces cost of \(g(e)\| (p_i-p_j) \|_2\). Similar to a proposal of Mirchandi for GOSST problems on graphs, the authors present a recursive approximation algorithm (RAA) and prove upper bounds on its worst-case-time-complexity at least for those cases, where there are at most 3 different grades of services. Next full Steiner topologics and their realisations are introduced and it is shown, that there is a full Steiner topology inducing a GOSST. For a given full Steiner topoly the grades of service for all edges can be computed in linear time: an \((1+\varepsilon)\)-approximation of a GOSST is computable in time polynomial in \(n\) and \(1/\varepsilon\). Although the number of full Steiner topologies is much less than the number of tree topologies a partial enumeration technique by backtracting may fail in large-scale-instances. The authors prove a bounding theorem, using topology vectors introduced by W. D. Smith, and propose some heuristis for the initial upper bound and for pruning subtrees in a branch-and-bound-framework; but experimental results show limited applicability. Therefore the authors propose a \(k\)-optimal heuristic algorithm -- with surprisingly good results, but no complexity analysis is given.