M.Sc Thesis | |

M.Sc Student | Beder Michael |
---|---|

Subject | Approximation Algorithms for Resource Scheduling and Allocation Problems |

Department | Department of Computer Science |

Supervisor | PROFESSOR EMERITUS Reuven Bar-Yehuda |

Full Thesis text |

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 *I _{j}* in

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 *I _{j}*
may be itself a bounded degree sub-tree of

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.