Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds.

We consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given jobs, represented as -dimensional vectors in , and identical machines, and the goal is to assign the jobs to machines such that the maximum of each machine over all the coordinates is at most 1. For fixed , the problem admits an approximation scheme, and the best known running time is where ( suppresses polylogarithmic terms in ). In particular, the dependence on is double exponential. In this paper we show that a double exponential dependence on is necessary, and give an improved algorithm with essentially optimal running time. Specifically, we let denote and show that: (1) For any , there is no -approximation with running time unless the Exponential Time Hypothesis fails. (2) No -approximation with running time exists, unless NP has subexponential time algorithms. (3) Similar lower bounds also hold even if extra machines are allowed (i.e. with resource augmentation), for sufficiently small . (4) We complement these lower bounds with a -approximation that runs in time . This gives the first efficient approximation scheme (EPTAS) for the problem.