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

Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha

Research output: Contribution to journalConference articlepeer-review

Abstract

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 languageEnglish (US)
Pages (from-to)114-123
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA
Duration: May 23 1998May 26 1998

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k-median'. Together they form a unique fingerprint.

Cite this