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 n jobs, represented as d-dimensional vectors in [Formula: see text] , and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of each machine over all the coordinates is at most 1. For fixed d, the problem admits an approximation scheme, and the best known running time is [Formula: see text] where [Formula: see text] ([Formula: see text] suppresses polylogarithmic terms in d). In particular, the dependence on d is double exponential. In this paper we show that a double exponential dependence on d is necessary, and give an improved algorithm with essentially optimal running time. Specifically, we let [Formula: see text] denote [Formula: see text] and show that: (1) For any [Formula: see text] , there is no [Formula: see text] -approximation with running time [Formula: see text] unless the Exponential Time Hypothesis fails. (2) No [Formula: see text] -approximation with running time [Formula: see text] exists, unless NP has subexponential time algorithms. (3) Similar lower bounds also hold even if [Formula: see text] extra machines are allowed (i.e. with resource augmentation), for sufficiently small [Formula: see text] . (4) We complement these lower bounds with a [Formula: see text] -approximation that runs in time [Formula: see text] . This gives the first efficient approximation scheme (EPTAS) for the problem.