Treffer: 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 $$[0,1]^d$$ , 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 $$n^{f(\epsilon ,d)}$$ where $$f(\epsilon ,d) = (1/\epsilon )^{\tilde{O}(d)}$$ ( $$\tilde{O}$$ 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 $$\exp (x)$$ denote $$2^x$$ and show that: (1) For any $$\epsilon <1$$ , there is no $$(1+\epsilon )$$ -approximation with running time $$\exp \left( o(\lfloor 1/\epsilon \rfloor ^{d/3})\right) $$ unless the Exponential Time Hypothesis fails. (2) No $$(1+\epsilon )$$ -approximation with running time $$\exp \left( \lfloor 1/\epsilon \rfloor ^{o(d)}\right) $$ exists, unless NP has subexponential time algorithms. (3) Similar lower bounds also hold even if $$\epsilon m$$ extra machines are allowed (i.e. with resource augmentation), for sufficiently small $$\epsilon >0$$ . (4) We complement these lower bounds with a $$(1+\epsilon )$$ -approximation that runs in time $$\exp \left( (1/\epsilon )^{O(d \log \log d)}\right) + nd$$ . This gives the first efficient approximation scheme (EPTAS) for the problem. [ABSTRACT FROM AUTHOR]

Copyright of Algorithmica is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)