Technical Report MSC-2013-04

Title: Approximation Algorithms for Resource Scheduling and Allocation Problems
Authors: Michael Beder
Supervisors: Reuven Bar-Yehuda
Abstract: 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2013
To the main CS technical reports page

Computer science department, Technion