Zpět na hledáníA lower bound for scheduling of unit jobs with immediate decision on parallel machines (2009)výskyt výsledku
Identifikační kód | RIV/67985840:_____/09:00334971 |
---|---|
Název v anglickém jazyce | A lower bound for scheduling of unit jobs with immediate decision on parallel machines |
Druh | D - Stať ve sborníku |
Jazyk | eng - angličtina |
Obor - skupina | I - Informatika |
Obor | IN - Informatika |
Rok uplatnění | 2009 |
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 | 2 |
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) |
Popis výsledku v anglickém jazyce | Consider scheduling of unit jobs with release times and deadlines on m. identical machines with the objective to maximize the number of jobs completed before their deadlines. We prove a new lower bound for online algorithms with immediate decision. Thismeans that the jobs arrive over time and the algorithm has to decide the schedule of each job immediately upon its release. Our lower bound tends to e/(e-1) approximate to 1.58 for many machines, matching the performance of the best algorithm. |
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 | - |
Údaje o výsledku v závislosti na druhu výsledku
Název sborníku | Approximation and online algorithms |
---|---|
ISBN | 978-3-540-93979-5 |
ISSN | - |
e-ISSN | - |
Počet stran výsledku | 10 |
Strana od-do | |
Název nakladatele | Springer |
Místo vydání | Berlin |
Místo konání akce | Karlsruhe |
Datum konání akce | 18.09.2008 |
Typ akce podle státní příslušnosti účastníků | WRD - Celosvětová |
Kód UT WoS článku podle Web of Science | 000264413000004 |
EID výsledku v databázi Scopus | - |
Ostatní informace o výsledku
Předkladatel | Matematický ústav AV ČR, v. v. i. |
---|---|
Dodavatel | AV0 - Akademie věd České republiky (AV ČR ) |
Rok sběru | 2010 |
Specifikace | RIV/67985840:_____/09:00334971!RIV10-AV0-67985840 |
Datum poslední aktualizace výsledku | 26.05.2010 |
Kontrolní číslo | 12203208 |
Informace o dalších výskytech výsledku dodaného stejným předkladatelem
Dodáno GA ČR v roce 2010 | RIV/67985840:_____/09:00334971 v dodávce dat RIV10-GA0-67985840/01:1 |
---|---|
Dodáno MŠMT v roce 2010 | RIV/67985840:_____/09:00334971 v dodávce dat RIV10-MSM-67985840/01:1 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
Projekt podporovaný AV ČR v programu IA | IAA1019401 - Teorie, důkazy a výpočetní složitost (2004 - 2008) |
---|---|
Výzkumný záměr podporovaný AV ČR | AV0Z10190503 - Rozvoj a prohloubení obecných matematických poznatků a jejich užití v dalších vědních oborech a v praxi (2005 - 2010) |