Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k-median

A recent result for probabilistically approximating graph metrics by trees such that no edge stretches by more than a factor of O(log²n) has resulted in several approximation algorithms which exploit the ease of solving problems on trees where tree construction is inherently randomized. A general framework for derandoming approximation algorithms which use the randomized tree construction as primitive is presented. Given an optimal solution to LP relaxation of the integer program, mapping of the solution to a tree approximation of the graph with at most a O(log n loglog n) blow-up in the value of the objective function. The framework is applied to the group Steiner tree, the k-median and the minimum communication cost spanning tree problems.