### Abstract

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 language | English |
---|---|

Title of host publication | LATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings) |

Editors | A. Pardo, A. Viola |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 47-59 |

ISBN (Print) | 978-3-642-54422-4 |

DOIs | |

Publication status | Published - 2014 |

Event | 11th Latin American Theoretical INformatics Symposium (LATIN 2014) - Montevideo, Uruguay Duration: 31 Mar 2014 → 4 Apr 2014 Conference number: 11 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 8392 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 11th Latin American Theoretical INformatics Symposium (LATIN 2014) |
---|---|

Abbreviated title | LATIN 2014 |

Country | Uruguay |

City | Montevideo |

Period | 31/03/14 → 4/04/14 |

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

## Cite this

Bansal, N., Vredeveld, T., & Zwaan, van der, G. R. J. (2014). Approximating vector scheduling: almost matching upper and lower bounds. In A. Pardo, & A. Viola (Eds.),

*LATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings)*(pp. 47-59). (Lecture Notes in Computer Science; Vol. 8392). Springer. https://doi.org/10.1007/978-3-642-54423-1_5