Computer Science – Data Structures and Algorithms
Scientific paper
2010-04-02
Computer Science
Data Structures and Algorithms
Scientific paper
We consider the problem of constructing a single spanning tree for the single-source buy-at-bulk network design problem for doubling-dimension graphs. We compute a spanning tree to route a set of demands (or data) along a graph to or from a designated root node. The demands could be aggregated at (or symmetrically distributed to) intermediate nodes where the fusion-cost is specified by a non-negative concave function $f$. We describe a novel approach for developing an oblivious spanning tree in the sense that it is independent of the number of data sources (or demands) and cost function at intermediate nodes. To our knowledge, this is the first paper to propose a single spanning tree solution to this problem (as opposed to multiple overlay trees). There has been no prior work where the tree is oblivious to both the fusion cost function and the set of sources (demands). We present a deterministic, polynomial-time algorithm for constructing a spanning tree in low doubling graphs that guarantees $\log^{3}D\cdot\log n$-approximation over the optimal cost, where $D$ is the diameter of the graph and $n$ the total number of nodes. With constant fusion-cost function our spanning tree gives a $O(\log^3 D)$-approximation for every Steiner tree to the root.
Busch Costas
Iyengar Sitharama
Srinivasagopalan Srivathsan
No associations
LandOfFree
An Oblivious Spanning Tree for Buy-at-Bulk Network Design Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Oblivious Spanning Tree for Buy-at-Bulk Network Design Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Oblivious Spanning Tree for Buy-at-Bulk Network Design Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-408053