The Taub Faculty of Computer Science Events and Talks

We study the bandwidth allocation problem (BAP) and the storage allocation problem (SAP) in bounded degree trees. In BAP, we are given a tree and a set of tasks. Each task consists of a path in the tree, a bandwidth demand, and a weight. Our goal is to find a maximum weight subset S of tasks such that, for every edge e, the total bandwidth of demand in S whose path contains e does not exceed the edge's capacity. In SAP it is also required that every task in the solution is given the same contiguous portion of the resource in every edge in its path. For BAP in bounded degree trees and uniform edge capacities, we present a deterministic ((2 sqrt(e) - 1)/(sqrt(e) - 1) + eps) < 3.542 approximation algorithm, based on a novel application of the Local Ratio technique. We also present a randomized (2 + eps) approximation algorithm, while the best previously known ratio for BAP in general trees is 5. We generalize our results for the case in which the tasks themselves are bounded degree trees. For BAP and SAP on the line and uniform edge capacities, we present a deterministic ((2e - 1)/(e - 1) + eps) < 2.582 approximation algorithm. We also present a randomized (2 + eps) approximation algorithm for SAP, while the best previously known ratio for this problem is 7. For SAP on the line and variable edge capacities, we present a (15 + eps) approximation algorithm, which is the first constant-factor approximation algorithm for this problem.