| Identifikační kód |
RIV/67985840:_____/06:00041413 |
| Název v anglickém jazyce |
A note on semi-online machine covering |
| Druh |
D - Stať ve sborníku |
| Jazyk |
eng - angličtina |
| Obor - skupina |
B - Fyzika a matematika |
| Obor |
BA - Obecná matematika |
| Rok uplatnění |
2006 |
| Kód důvěrnosti údajů |
S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku |
3 |
| Počet tvůrců celkem |
4 |
| Počet domácích tvůrců |
2 |
| Výčet všech uvedených jednotlivých tvůrců |
Tomáš Ebenlendr (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7083556)
Jiří Sgall (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 8679673)
E. J. Noga (státní příslušnost: US - Spojené státy americké)
G. Woeginger (státní příslušnost: NL - Nizozemsko) |
| Popis výsledku v anglickém jazyce |
In the machine cover problem we are given $m$ machines and $n$ jobs to be assigned (scheduled) so that the smallest load of a machine is as large as possible. A semi-online algorithms is given in advance the optimal value of the smallest load for the given instance, and then the jobs are scheduled one by one as they arrive, without any knowledge of the following jobs. We present a deterministic algorithm with competitive ratio $11/6/leq 1.834$ for machine covering with any number of machines and a lowerbound showing that no deterministic algorithm can have a competitive ratio below $43/24/geq 1.791$. |
| Klíčová slova oddělená středníkem |
online algorithms; scheduling |
| Stránka www, na které se nachází výsledek |
- |
| Odkaz na údaje z výzkumu |
- |