APPROXIMATION ALGORITHMS FOR SP-MULTICAST TREES IN 2D GRIDS

摘要

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.