Omezené typy výpočtů: algoritmy, modely, složitost
Cíle projektu
V tomto projektu základního výzkumu se soustředíme na roli omezených typů výpočtů v teorii složitosti a v teorii algoritmů. Budeme studovat problémy, pro které zkoumání omezených typů výpočtů může vést k podstatně silnějším a těsnějším dolním a horním odhadům složitosti a kvality algoritmů ve srovnání s tradičním studiem neomezených výpočtů. Ve výpočetní složitosti budeme studovat kombinatorické algoritmy pro problémy jako násobení booleovských matic a 3SUM, což je omezená varianta problému hledání podmnožiny s daným součtem. V algoritmické části projektu se zaměříme na online a aproximační algoritmy pro omezené varianty problému bin packing s omezeným prostorem, rozvrhování s cílem maximalizovat cenu splněných úloh a toky s omezenou délkou.
Klíčová slova
Computational complexitytheory of algorithmsonline algorithmsapproximation algorithmsschedulingcombinatorial algorithmsmatrix multiplicationlower bounds
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 18 (SGA0201400001)
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
14-10003S
Alternativní jazyk
Název projektu anglicky
Restricted computations: Algorithms, models, complexity
Anotace anglicky
In this project of basic research we focus on the role of restricted models of computation in complexity theory and theory of algorithms. We shall investigate problems for which studying the restricted scenarios may result in significantly stronger and closer lower and upper bounds on the complexity and performance of algorithms, compared to the traditional unrestricted scenarios. In computational complexity we shall study combinatorial algorithms for problems such as Boolean matrix multiplication and 3SUM, which is a restricted variant of the subset sum problem. In the algorithmic part of the project we shall focus on online and approximation algorithms for restricted variants of bounded space bin packing, throughput scheduling and length-bounded flows. The results will be published in high-quality international journals and proceedings of selective conferences in theoretical computer science.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
IN - Informatika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Projekt přinesl několik excelentních vědeckých výsledků na nejvyšší světové úrovni (třebaže klíčový člen týmu souběžně řešil ERC grant) a mnohé další kvalitní a mezinárodně srovnatelné výsledky. Zmíníme především konference STOC, SODA a ESA. Je vidět, že bylo dosaženo významného pokroku ve všech slibovaných směrech a navíc v ještě v přidané oblasti streaming algoritmů.
Termíny řešení
Zahájení řešení
1. 1. 2014
Ukončení řešení
31. 12. 2016
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
12. 4. 2016
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
CEP17-GA0-GA-U/03:1
Datum dodání záznamu
28. 6. 2017
Finance
Celkové uznané náklady
4 300 tis. Kč
Výše podpory ze státního rozpočtu
4 300 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
4 300 tis. Kč
Statní podpora
4 300 tis. Kč
100%
Poskytovatel
Grantová agentura České republiky
CEP
IN - Informatika
Doba řešení
01. 01. 2014 - 31. 12. 2016