Jain's technique of Iterative Rounding has recently developed into one of the premier tools for developing approximation algorithms for network design optimization problems, where the most notable recent success is undoubtedly Singh & Lau's '+1' approximation algorithm for the Minimum-Degree-Bounded Spanning Tree problem (BST).

In this talk, we present a further refinement to the technique of Iterative Rounding. In particular, we consider the following generalization of BST which is known as the Crossing Spanning Tree problem (CST): given an undirected graph G=(V,E), a non-negative cost c_e for every edge e in E, a family of vertex sets S_1,...,S_k, and non-negative integer degree bounds b_1,...,b_k, find a minimum cost spanning tree T that has at most b_i edges crossing S_i, for all i.

Bilo et al. were the first to consider this problem. The authors presented a (randomized) algorithm that finds a spanning tree with expected cost O(log n)*opt that crosses each set S_i O(log n)*b_i + O(log k) times with high probability. Recently, Kiraly et al. and, independently, Bansal et al. showed that one can compute a minimum-cost tree that crosses each set S_i at most b_i + (\Delta - 1) if each edge crosses at most \Delta sets.

In this talk we show how these two guarantees can be improved if the given sets have additional structure.

This is joint work with Nikhil Bansal, Rohit Khandekar, Viswanath Nagarajan & Britta Peis.