M.Sc Thesis

M.Sc StudentBeder Michael
SubjectApproximation Algorithms for Resource Scheduling and
Allocation Problems
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Reuven Bar-Yehuda
Full Thesis textFull thesis text - English Version


We study several problems in the field of combinatorial optimization, and specifically a family of resource scheduling and allocation problems.

In the Unsplittable Flow Problem in Trees (UFPT) we have an edge-capacitated tree T = (V,E), and a set J of tasks. Each task j is associated with a path Ij in T, a bandwidth demand dj, and a weight wj that may be gained by accommodating it. A feasible solution, or a schedule, is a subset S of J of tasks such that, for every edge e, the total demand of tasks whose path contains e is at most the edge's capacity ce. Our goal is to find a schedule with maximum total weight.

The Contiguous Flow Problem in Trees (CFPT) is a variant of UFPT in which there is an additional constraint: it is also required that every task in the solution is given the same contiguous portion of the resource in every edge along its path.

Furthermore, where T is uniformly capacitated, i.e. all edges have a capacity of 1, UFPT and CFPT become the Bandwidth Allocation Problem in Trees (BAPT) and the Storage Allocation Problem in Trees (SAPT), respectively.

We present several polynomial time approximation algorithms. For BAPT in bounded degree trees, we present a deterministic

 (2√e - 1)/( √e - 1) ε < 3.542 approximation algorithm, based on a novel application of the Local Ratio technique. We also present a randomized (2 ε)-approximation algorithm, while the best previously known approximation ratio for BAPT in general trees is 5. We generalize our results for the case where Ij may be itself a bounded degree sub-tree of T.

For BAPT and SAPT on the line, we present a deterministic (2e - 1)/(e - 1) ε < 2.582 approximation algorithm. We also present a randomized (2 ε)-approximation algorithm for SAPT on the line, by that improving the best previously known ratio of 7.

For CFPT on the line, namely CFPL, we present a (9 ε)-approximation algorithm. We also show that CFPL is strongly NP-hard, even with uniform weights and even if assuming the no-bottleneck assumption.