Teofilo F. Gonzalez
Approximation algorithms, 2d-grid network, sp-multicast trees, mul-ticast, rectilinear Steiner tree arborescence
We study the problem of constructing shortest path multicast (sp-multicast) trees for transmitting a message from a node to a set of destinations in 2d-grid networks. We present an integer linear programming (ILP) formulation of the problem and its relaxed linear program (LP). We evaluate the solutions generated by solving the LP problem for 500,000 randomly generated problem instances. We present a global rounding scheme that given any half-integral LP optimal solution, it generates a solution to the sp-multicast problem within 1.5 times the optimal solution value. We also discuss an improved rounding scheme.
Important Links:
Go Back
