Approximating buy-at-bulk and shallow-light k-Steiner trees

M. T. Hajiaghayi, G. Kortsarz, M. R. Salavatipour

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V, E) with a set of terminals T ⊆ V including a particular vertex s called the root, and an integer k ≤ |T|. There are two cost functions on the edges of G, a buy cost b : E → ℝ+ and a distance cost r : E → ℝ+. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑e∈Hb(e) + ∑t∈T-s dist(t, s) is minimize, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log 4 n)-approximation for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e) over the edges, and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log n), O(log3 n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least k/8 terminals. Using this we obtain an (O(log2 n), O(log4 n))-approximation for the shallow-light k-Steiner tree and an O(log4 n)-approximation for the buy-at-bulk k-Steiner tree problem.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 a
PublisherSpringer Verlag
Pages152-163
Number of pages12
ISBN (Print)3540380442, 9783540380443
DOIs
StatePublished - 2006
Event9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006 - Barcelona, Spain
Duration: Aug 28 2006Aug 30 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4110 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006
CountrySpain
CityBarcelona
Period8/28/068/30/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximating buy-at-bulk and shallow-light k-Steiner trees'. Together they form a unique fingerprint.

Cite this