Omezené typy výpočtů: algoritmy, modely, složitost

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

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.

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 <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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ů.

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

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

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č