We study the design of schedules for multi-commodity multicast. In this problem, we are given an undirected graph $G$ and a collection of source-destination pairs, and the goal is to schedule a minimum-length sequence of matchings that connects every source with its respective destination. Multi-commodity multicast models a classic information dissemination problem in networks where the primary communication constraint is the number of connections that a given node can make, not link bandwidth. Multi-commodity multicast and its special cases, broadcast and multicast, are all NP-complete and the best approximation factors known are $2^{\widetilde{O}(\sqrt{\log n})}$, $O(\log n/\log\log n)$, and $O(\log k/\log\log k)$, respectively, where $n$ is the number of nodes and $k$ is the number of terminals in the multicast instance. #R##N#Multi-commodity multicast is closely related to the problem of finding a subgraph of optimal poise, where the poise is defined as the sum of the maximum degree of the subgraph and the maximum distance between any source-destination pair in the subgraph. We first show that for any instance of the multicast problem, the minimum poise subgraph can be approximated to within a factor of $O(\log k \log n)$ with respect to the value of a natural LP relaxation in an $n$-node graph with $k$ source-destination pairs. This is the first upper bound on the integrality gap of the natural LP; all previous algorithms, both combinatorial and LP-based, yielded approximations with respect to the integer optimum. Using this integrality gap upper bound, we obtain our main result: an $O(\log^2 k\log^2 n)$-approximation for multi-commodity multicast for planar graphs. In addition, the techniques used also give an $O(\log^2 n)$-approximation for radio gossip in planar graphs. This is the first bound for radio gossip given that doesn't rely on the maximum degree of the graph.
['Jennifer Iglesias', 'Rajmohan Rajaraman', 'R. Ravi', 'Ravi Sundaram']
Plane Gossip: Approximating rumor spread in planar graphs