Pravděpodobnostní kompetitivní algoritmy pro online problémy
Cíle projektu
Praktické optimalizační problémy mají často tzv. online charakter, tj. vstupní data nejsou známa předem, ale požadavky přicházejí postupně a je nutné na ně reagovat bez znalosti dalšího vstupu. Budeme studovat pravděpodobnostní algoritmy pro takovéto problémy, a to jednak na konkrétních problémech, zejména z oblasti rozvrhování a tzv. server problémů, a jednak obecnější metody jejich konstrukce.
Klíčová slova
algorithmoptimizationon-linecompetitive analysisschedulingserver problems
Veřejná podpora
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
Program
KONTAKT
Veřejná soutěž
KONTAKT 1 (SMSM200132001)
Hlavní účastníci
Matematický ústav AV ČR, v. v. i.
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
—
Alternativní jazyk
Název projektu anglicky
Randomized competitive algorithm for online problems
Anotace anglicky
Practical optimization problems are often on-line, i.e., the input data is not known in advance, instead the algorithm has to satisfy the requests as they arrive, without the knowledge of the future input. We plan to study randomized algorithms for suchconcrete problems, focusing on the areas of scheduling and so-called server problems, as well as general methods for design of such algorithms.
Vědní obory
Kategorie VaV
—
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10101 - Pure mathematics
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Základní výzkum v oblsti online algoritmů.nejvýzn. výsledky z oblasti rozvrhování, tzv. preemptivního rozvrhování a rozvrhování přetížených systémů.
Termíny řešení
Zahájení řešení
1. 1. 2001
Ukončení řešení
1. 1. 2003
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
—
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP/2004/MSM/MSM4ME/U/N/4:2
Datum dodání záznamu
3. 6. 2008
Finance
Celkové uznané náklady
774 tis. Kč
Výše podpory ze státního rozpočtu
435 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
339 tis. Kč
Uznané náklady
774 tis. Kč
Statní podpora
435 tis. Kč
0%
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
CEP
BA - Obecná matematika
Doba řešení
01. 01. 2001 - 01. 01. 2003