# Approximating vector scheduling: almost matching upper and lower bounds

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

5 Citaten (Scopus)

## Samenvatting

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-2 Engels LATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings) A. Pardo, A. Viola Berlin Springer 47-59 978-3-642-54422-4 https://doi.org/10.1007/978-3-642-54423-1_5 Gepubliceerd - 2014 11th Latin American Theoretical INformatics Symposium (LATIN 2014) - Montevideo, UruguayDuur: 31 mrt. 2014 → 4 apr. 2014Congresnummer: 11

### Publicatie series

Naam Lecture Notes in Computer Science 8392 0302-9743

### Congres

Congres 11th Latin American Theoretical INformatics Symposium (LATIN 2014) LATIN 2014 Uruguay Montevideo 31/03/14 → 4/04/14 11th Latin American Symposium on Theoretical Informatics

## Vingerafdruk

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