# 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

4 Citations (Scopus)

## 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 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 Published - 2014 11th Latin American Theoretical INformatics Symposium (LATIN 2014) - Montevideo, UruguayDuration: 31 Mar 2014 → 4 Apr 2014Conference number: 11

### Publication series

Name Lecture Notes in Computer Science 8392 0302-9743

### Conference

Conference 11th Latin American Theoretical INformatics Symposium (LATIN 2014) LATIN 2014 Uruguay Montevideo 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.