Teofilo F. Gonzalez
Approximation algorithms, 2d-grid network, sp-multicast trees, multicast, 2d-grid network, sp-multicast trees, multicast, rectilinear Steiner tree arborescence
We study the problem of constructing a shortest path multicast (sp-multicast) tree for transmitting a message from a node, s, to a set of destinations, D, in 2d-grid networks. We show that the performance analysis of the previous 2-approximation algorithms is best possible. Given any half-integral optimal solution, we present a global rounding scheme that generates solutions that are within 1.5 times the optimal solution value. Our algorithm is different from previous ones in the sense that it is not based on simple heuristics or brute force approaches, it is based on a global rounding strategy. Our analysis uses a sharper lower bound.
Important Links:
Go Back
