AN EFFICIENT APPROXIMATION ALGORITHM FOR HYPERCUBE SCHEDULING

Given a set of m tasks, where each task has an execution time and a subcube requirement, the Hypercube Scheduling Problem (HSP) is to find an assignment of tasks which minimizes the total completion time. The general HSP is known to be NP-hard. In this paper, we present a O(m log m) time algorithm for HSP when all the m tasks have the same execution time. We also present a polynomial time approximation algorithm which generates a solution within [GRAPHICS] of the optimal solution for the general HSP, where n is the hypercube dimension.