The buffer minimization problem for multiprocessor scheduling with conflicts.
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F01%3A05025170" target="_blank" >RIV/67985840:_____/01:05025170 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
The buffer minimization problem for multiprocessor scheduling with conflicts.
Popis výsledku v původním jazyce
Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. In the on-line case, we provide the following results: (i) a competitive algorithm for general graphs, (ii) tight bounds on the competitive ratios for cliques and complete $k$-partite graphs, and (iii) a $(Delta/2+1)$-competitive algorithm for trees, where $Delta$ is the diameter.
Název v anglickém jazyce
The buffer minimization problem for multiprocessor scheduling with conflicts.
Popis výsledku anglicky
Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. In the on-line case, we provide the following results: (i) a competitive algorithm for general graphs, (ii) tight bounds on the competitive ratios for cliques and complete $k$-partite graphs, and (iii) a $(Delta/2+1)$-competitive algorithm for trees, where $Delta$ is the diameter.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2001
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of the 28th International Colloquium on Automata, Languages, and Programming.
ISBN
—
ISSN
—
e-ISSN
—
Počet stran výsledku
13
Strana od-do
862-874
Název nakladatele
Springer-Verlag
Místo vydání
Berlin
Místo konání akce
Crete [GR]
Datum konání akce
8. 7. 2001
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—