Fall 2017

LP Rounding for Poise

Tuesday, Sep. 12, 2017 4:00 pm4:30 pm PDT

Add to Calendar

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

Joint work with Jennifer Iglesias (Carnegie Mellon University), Rajmohan Rajaraman (Northeastern) and Ravi Sundaram (Northeastern)

PDF icon LP Rounding for Poise1.09 MB