Abstract
The poise of a spanning tree in an undirected graph is the sum of its diameter and its maximum degree. Finding Steiner trees of minimum poise have applications for the design of fast multicast schemes among the terminals. We present an O(log k) approximation algorithm for minimum poise Steiner tree on k terminals with respect to its natural LP relaxation. This in turn finds use in the first poly-logarithmic approximation algorithms for multicommodity multicast problems in planar graphs. (Details in https://arxiv.org/abs/1612.01492)
Joint work with Jennifer Iglesias (Carnegie Mellon University), Rajmohan Rajaraman (Northeastern) and Ravi Sundaram (Northeastern)