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 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
PublisherSpringer
Pages47-59
ISBN (Print)978-3-642-54422-4
DOIs
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
Volume8392
ISSN (Print)0302-9743

Conference

Conference11th Latin American Theoretical INformatics Symposium (LATIN 2014)
Abbreviated titleLATIN 2014
CountryUruguay
CityMontevideo
Period31/03/144/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