Approximating vector scheduling: almost matching upper and lower bounds

N. Bansal, T. Vredeveld, G.R.J. Zwaan, van der

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)


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 {\em 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}$ supresses polylogarithmic terms in $d$). In particular, the dependence on $d$ is doubly exponential. In this paper we show that a double exponential dependence on $d$ is necessary, and give an improved algorithm with essentially optimum running time. Specifically, we show that: \begin{itemize} \item For any $\epsilon0$. \item We complement these lower bounds with a $(1+\epsilon)$-approximation that runs in time $\exp((1/\epsilon)^{O(d \log \log d)}) + nd$. This gives the first efficient approximation scheme (EPTAS) for the problem. \end{itemize}
Original languageEnglish
Title of host publicationLATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings)
EditorsA. Pardo, A. Viola
Place of PublicationBerlin
ISBN (Print)978-3-642-54422-4
Publication statusPublished - 2014
Event11th Latin American Theoretical INformatics Symposium (LATIN 2014) - Montevideo, Uruguay
Duration: 31 Mar 20144 Apr 2014
Conference number: 11

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference11th Latin American Theoretical INformatics Symposium (LATIN 2014)
Abbreviated titleLATIN 2014


Dive into the research topics of 'Approximating vector scheduling: almost matching upper and lower bounds'. Together they form a unique fingerprint.

Cite this