Approximating vector scheduling: almost matching upper and lower bounds

Autor: Nikhil Bansal, Tim Oosterwijk, Tjark Vredeveld, Ruben van der Zwaan
Přispěvatelé: Discrete Mathematics, Combinatorial Optimization 1, QE Operations research, RS: GSBE ETBC
Jazyk: angličtina
Rok vydání: 2016
Předmět:
Zdroj: Algorithmica, 76(4), 1077-1096. Springer
Algorithmica
Algorithmica, 76(4), 1077-1096. Springer Verlag
ISSN: 0178-4617
Popis: 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[0,1]^d$$\end{document}[0,1]d, and m identical machines, and the goal is to assign the jobs to machines such that the maximum 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n^{f(\epsilon ,d)}$$\end{document}nf(ϵ,d) where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(\epsilon ,d) = (1/\epsilon )^{\tilde{O}(d)}$$\end{document}f(ϵ,d)=(1/ϵ)O~(d) (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{O}$$\end{document}O~ suppresses polylogarithmic terms in d). In particular, the dependence on d is double exponential. In this paper we show that a double exponential dependence on d is necessary, and give an improved algorithm with essentially optimal running time. Specifically, we let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exp (x)$$\end{document}exp(x) denote \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^x$$\end{document}2x and show that: (1) For any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon 0$$\end{document}ϵ>0. (4) We complement these lower bounds with a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1+\epsilon )$$\end{document}(1+ϵ)-approximation that runs in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exp \left( (1/\epsilon )^{O(d \log \log d)}\right) + nd$$\end{document}exp(1/ϵ)O(dloglogd)+nd. This gives the first efficient approximation scheme (EPTAS) for the problem.
Databáze: OpenAIRE
Externí odkaz: