SP-MULTICAST TREES FOR GRIDS

摘要

We study the problem of constructing a shortest path multicastrn(sp-multicast) tree for transmitting a message from arnnode, s, to a set of destinations, D, in 2d-grid networks.rnWe show that the performance analysis of the previousrn2-approximation algorithms is best possible. Given anyrnhalf-integral optimal solution, we present a global roundingrnscheme that generates solutions that are within 1.5 timesrnthe optimal solution value. Our algorithm is different fromrnprevious ones in the sense that it is not based on simplernheuristics or brute force approaches, it is based on a globalrnrounding strategy. Our analysis uses a sharper lower bound.