Polynomial time approximation scheme for general multiprocessor job scheduling
Conference Paper
Overview
Additional Document Info
View All
Overview
abstract
Recently, there have been considerable interests in the multiprocessor job scheduling problem, in which a job can be processed in parallel on one of several alternative subsets of processors. In this paper, a polynomial time approximation scheme is presented for the problem in which the number of processors in the system is a fixed constant. This result is the best possible because of the strong NP-hardness of the problem, and is a significant improvement over the past results: the best previous result was an approximation algorithm of ratio 7/6+ for 3-processor systems, based on Goemans' algorithm for a restricted version of the problem.
name of conference
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA