DIMACS TR: 2006-24

Approximation algorithms for a Resource Allocation Problem

Author: Srikrishnan Divakaran


In this paper, we present approximation algorithms for a resource allocation problem that arises in the context of processor allocation among parallel tasks in massively parallel super computers. In this paper, we consider a processor allocation problem, where we are given a computing grid consisting of a set of processors connected in the form of an linear or circular list. When a job arrives, a set of available processors from the grid is assigned to that job. One of the objectives in allocating processors is to minimize communication overheads caused by overlapping jobs. That is, assign processors to minimize communication overheads caused by non-contiguous allocation of processors.

The processor problem is a variant of the two-dimensional packing problem, where objects have placement constraints and are allowed to be split into smaller objects. This problem also has applications in the design of algorithms for bandwidth allocation in computer networks and memory management in computer systems.

For the $MaxStretch$ and $TotalStretch$ metrics, the offline version of processor allocation problem is known to be strongly $NP$ Hard. For the online version, it is known that the best achievable competitive ratio for even a randomized algorithm is $\Omega(n)$.

In this paper, we analyze the processor allocation problem in a relaxed framework, where our algorithm is given $O(1)$ more processors than the optimal offline algorithm. In this framework, for the MaxStretch and TotalStretch metrics, we present algorithms that obtains an optimal solution for the following two special cases:

Key Words: Analysis of algorithms; Operations Research; Approximation algorithms; Online algorithms; Resource Allocation; Multi-dimensional Bin Packing

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-24.ps.gz
DIMACS Home Page