Approximation Algorithms for Resource Scheduling and Allocation Problems

Michael Beder (M.Sc. Thesis Seminar)

Wednesday, 27.06.2012, 11:30

Taub 601

Advisor: Prof. R. Bar-Yehuda

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.