Zobrazeno 1 - 10
of 38
pro vyhledávání: '"Theory of computation ��� Scheduling algorithms"'
Massive surges of enrollments in courses have led to a crisis in several computer science departments - not only is the demand for certain courses extremely high from majors, but the demand from non-majors is also very high. Much of the time, this le
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9e3684b024384111359166fc4bfede96
http://arxiv.org/abs/2304.07982
http://arxiv.org/abs/2304.07982
In this paper we study two fully-dynamic multi-dimensional vector load balancing problems with recourse. The adversary presents a stream of n job insertions and deletions, where each job j is a vector in ℝ^d_{≥ 0}. In the vector scheduling proble
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::32172a1b62de8fe3303a7d4e8c41cb0d
Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimize some objective. This framework captures a broad range of fundamenta
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cb692a2b3a66b6389651fe242dfc111f
We study the problem of scheduling precedence-constrained jobs on heterogenous machines in the presence of non-uniform job and machine communication delays. We are given a set of n unit size precedence-ordered jobs, and a set of m related machines ea
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aca25f9e3168bd36256528c470fcc7f9
Autor:
Buchem, Moritz, Rohwedder, Lars, Vredeveld, Tjark, Wiese, Andreas, Bansal, Nikhil, Merelli, Emanuela, Worrell, James
Publikováno v:
Proceedings of 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198(LIPIcs), 42:1-42:17
STARTPAGE=73;ENDPAGE=76;TITLE=15th Workshop on Models and Algorithms for Planning and Scheduling 2022
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 1-17
STARTPAGE=1;ENDPAGE=17;TITLE=48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Buchem, M, Rohwedder, L, Vredeveld, T & Wiese, A 2021, Additive Approximation Schemes for Load Balancing Problems . in N Bansal, E Merelli & J Worrell (eds), 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) ., 42, Leibniz International Proceedings in Informatics, LIPIcs, vol. 198, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, pp. 1-17 . https://doi.org/10.4230/LIPIcs.ICALP.2021.42
STARTPAGE=73;ENDPAGE=76;TITLE=15th Workshop on Models and Algorithms for Planning and Scheduling 2022
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 1-17
STARTPAGE=1;ENDPAGE=17;TITLE=48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Buchem, M, Rohwedder, L, Vredeveld, T & Wiese, A 2021, Additive Approximation Schemes for Load Balancing Problems . in N Bansal, E Merelli & J Worrell (eds), 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) ., 42, Leibniz International Proceedings in Informatics, LIPIcs, vol. 198, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, pp. 1-17 . https://doi.org/10.4230/LIPIcs.ICALP.2021.42
We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most ε h for some suitable para
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0dd224794c2317a927cadf6237bf746b
https://hdl.handle.net/1871.1/7c079977-53a0-4457-9e49-0c963d15a101
https://hdl.handle.net/1871.1/7c079977-53a0-4457-9e49-0c963d15a101
We consider variants of the restricted assignment problem where a set of jobs has to be assigned to a set of machines, for each job a size and a set of eligible machines is given, and the jobs may only be assigned to eligible machines with the goal o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::316e063e8af93f9d64a44db2ed794d82
http://arxiv.org/abs/2203.06171
http://arxiv.org/abs/2203.06171
The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::40b76dd221f2cddfe694481004a1fb55
Autor:
Kuszmaul, William, Narayanan, Shyam
The p-processor cup game is a classic and widely studied scheduling problem that captures the setting in which a p-processor machine must assign tasks to processors over time in order to ensure that no individual task ever falls too far behind. The p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::74bb4e74d3f6813fa130000087f1dd22
Autor:
Das, Syamantak, Wiese, Andreas
We study the classical scheduling problem of minimizing the makespan of a set of unit size jobs with precedence constraints on parallel identical machines. Research on the problem dates back to the landmark paper by Graham from 1966 who showed that t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::466e8cafd80b8f168bf2ffcaa9cc3295
We provide new (parameterized) computational hardness results for Interval Scheduling on Unrelated Machines. It is a classical scheduling problem motivated from just-in-time or lean manufacturing, where the goal is to complete jobs exactly at their d
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3621a92a9ab6a95d3c78d6b75b3c2a3e