An Oblivious Spanning Tree for Single-Sink Buy-at-Bulk in Low Doubling-Dimension Graphs

Abstract—We consider the problem of constructing a single spanning tree for the single-sink buy-at-bulk network design problem for doubling-dimension graphs. We compute a spanning tree to route a set of demands along a graph G to or from a designated sink node. The demands could be aggregated at (or symmetrically distributed to) intermediate edges where the fusion cost is specified by a nonnegative concave function f. We describe a novel approach for developing an oblivious spanning tree in the sense that it is independent of the number and location of data sources (or demands) and cost function at the edges. We present a deterministic, polynomial-time algorithm for constructing a spanning tree in low doubling-dimension graphs that guarantees a log3D-approximation over the optimal cost, where D is the diameter of the graph G. With a constant fusion-cost function, our spanning tree gives an Oðlog3DÞ-approximation for every Steiner tree that includes the sink. We also provide a ðlognÞ lower bound for any oblivious tree in low doubling-dimension graphs. To our knowledge, this is the first paper to propose a single spanning tree solution to the single-sink buy-at-bulk network design problem (as opposed to multiple overlay trees). Index Terms—Spanning tree, buy-at-bulk, network design, approximation algorithm, doubling-dimension graph, data fusion, data structure. Ç