 |
Center for Nonlinear Studies |
Network design is a fundamental problem that has applications in communication networks, VLSI design, pipeline network optimization, transportation and logistics etc. The goal of network design is to find paths through various points of a network in such a way that the total cost of routing the demands along the network from sources to destination(s) is minimized. The demands could be aggregated at (or symmetrically distributed to) intermediate edges where the fusion-cost is specified by a non-negative concave function f. This is often called “discrete cost network optimization” in Operations Research and is proven to be NP-Complete. In this context, my talk will focus on the results of my recent research study funded by NSF and DEPSCoR - Oblivious Buy-at-Bulk Network Design, where, the computation of a near-optimal network considers economies of scale and is done without prior knowledge of the set of sources and the fusion cost function. The notion of Buy-at-Bulk refers to the concept of transporting things in “wholesale” or “volume discount” (such as network capacity, where cost per bandwidth decreases as the number of bandwidth units purchased increases). I consider two scenarios – Single-Sink Buy-at-Bulk (SSBB), where the network will have only one sink (or destination node). I will give an overview of a deterministic, polynomial-time algorithm that computes a spanning tree which guarantees a good approximation on Doubling-Dimension graphs. The other scenario is Multi-Sink Buy-at-Bulk (MSBB), where there are multiple sinks. In this case, I will present the basic idea behind a deterministic, polynomial time algorithm on planar graphs that provides a set of paths which guarantees asymptotically tight bound.
Host: Aric Hagberg, hagberg@lanl.gov, 665-4958