Approximating vector scheduling: almost matching upper and lower bounds

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 Citaten (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}
Originele taal-2Engels
TitelLATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings)
RedacteurenA. Pardo, A. Viola
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-54422-4
StatusGepubliceerd - 2014
Evenement11th Latin American Theoretical INformatics Symposium (LATIN 2014) - Montevideo, Uruguay
Duur: 31 mrt. 20144 apr. 2014
Congresnummer: 11

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Congres11th Latin American Theoretical INformatics Symposium (LATIN 2014)
Verkorte titelLATIN 2014
Ander11th Latin American Symposium on Theoretical Informatics


Duik in de onderzoeksthema's van 'Approximating vector scheduling: almost matching upper and lower bounds'. Samen vormen ze een unieke vingerafdruk.

Citeer dit