A recent result for probabilistically approximating graph metrics by trees such that no edge stretches by more than a factor of O(log2n) 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.
|Original language||English (US)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1998|
|Event||Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA|
Duration: May 23 1998 → May 26 1998
ASJC Scopus subject areas